Backtracking & Dynamic Programming & Greedy

Posted on | In , |

Greedy

Backtracking

permutation

Recursive Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def permute(nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    if len(nums) < 1:
        return [nums]
    perms = []
    for idx, num in enumerate(nums):
        for perm in permute(nums[:idx] + nums[idx+1:]):
            perms.append([num] + perm)
    return perms
def permuteUnique(self, nums):
    if len(nums) <= 1:
        return [nums]
    res = []
    nums.sort()
    prev = None
    for idx, num in enumerate(nums):
        # skip duplicated num
        if num == prev:
            continue
        else:
            for perm in self.permuteUnique(nums[:idx] + nums[idx+1:]):
                res.append([num] + perm)
            prev = num
    return res

combination

  • do we have duplications?
  • do we keep the continuous selections
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
    # choose(n,k)
    def recursive_helper(self,res, n, i, k, tmp):
        if k == 0:
            res.append(tmp)
            return
        for j in range(i+1, n+1):
            self.recursive_helper(res, n, j, k-1, tmp + [j])
    def combine(self, n, k):
        if n < k or k <=0 or n <=0:
            return []
        res = []
        # recursive
        self.recursive_helper(res, n, 0, k, [])
        return res
OR
def combine(self, n, k):
    if k == 0:
        return [[]]
    return [pre + [i] for i in range(k, n+1) for pre in self.combine(i-1, k-1)]

Subset

1
2
3
4
5
6
7
def subsets(self, nums):
    if not nums:
        return [[]]
    res = [[]]
    for num in nums:
        res += [[num] + r for r in res]
    return res

Divide and conquer
https://leetcode.com/problems/create-maximum-number/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution(object):
    def maxNumber(self, nums1, nums2, k):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type k: int
        :rtype: List[int]
        """
        def get_max(nums, t):
            res = []
            N = len(nums)
            for i in range(N):
                while res and N - i  > t - len(res) and res[-1] < nums[i]:
                    res.pop()
                if len(res) < t:
                    res.append(nums[i])
            return res
        
        def merge_max(nums1, nums2):
            ans = []
            while nums1 or nums2:
                if nums1 > nums2:
                    ans += nums1[0],
                    nums1 = nums1[1:]
                else:
                    ans += nums2[0],
                    nums2 = nums2[1:]
            return ans
        
        res = None
        N1, N2 = len(nums1), len(nums2)
        for t in range(max(0, k - N2), min(k, N1) +1):
            tmp_res = merge_max(get_max(nums1, t), get_max(nums2, k-t))
            res = max(tmp_res, res) if res else tmp_res
        return res