Summary

• DFS problems have two kinds: One to get the number of all solutions. The other is to get all the solutions itself.
  
  • To get the total number of solutions, usually you can use dynamic programming.
  • To get all the solution, there is a fixed solution style. And you need to determine where it doesn’t give out.

# main method 
res = []
self.helper(....)
return res

# auxiliary method
def helper(...):
    if proper:
        res.append()
        return
    for x in xrange(start,end):
        do something
        self.helper(...)
        undo something

leetcode 46 Permutations

Question

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

Solution

recursion swap

Swap the current value and each of the values followed, then solve the rest permutation.

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        self.helper(nums,0,res)
        return res

    def helper(self,nums,start,res):
        if start == len(nums):
            res.append(list(nums))
            return
        for i in xrange(start,len(nums)):
            if not self.contain_duplication(nums,start,i):
                nums[start],nums[i] = nums[i],nums[start]
                self.helper(nums,start+1,res)
                nums[start],nums[i] = nums[i],nums[start]
    def contain_duplication(self,nums,start,end):
        for i in xrange(start,end):
            if nums[i] == nums[end]:
                return True

• increase insert
  Every turn add a value in every possible position, and next turn and the new value on the base of the last turn. Use set to delete the duplication.

class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        res.append([])
        for i in xrange(len(nums)):
            s = set()
            for lst in res:
                for j in xrange(len(lst)+1):
                    lst.insert(j,nums[i])
                    s.add(tuple(lst))
                    del lst[j]
            res = [list(t) for t in s]
        return res

leetcode 77 Combinations

Question

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

For example,
If n = 4 and k = 2, a solution is:

[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

Solution

Recursion, when find a solution, back to the next value.

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        self.helper(n,k,[],res,1)
        return res

    def helper(self, n, k, lst, res, start):
        if len(lst) == k:
            res.append(list(lst))
            return
        for i in xrange(start,n+1):
            lst.append(i)
            self.helper(n,k,lst,res,i+1)
            lst.pop()

leetcode 39 Combination Sum

Question

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Solution

Different from above, this time it is allowed to reuse the elements, So you have to start at i, not i+1.

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        self.helper(candidates,0,target,[],res)
        return res

    def helper(self,candidates,start,target,lst,res):
        if target == 0:
            res.append(list(lst))
            return
        elif target < 0:
            return
        for i in xrange(start,len(candidates)):
            if i == start or candidates[i] != candidates[i-1]: 
                lst.append(candidates[i])
                self.helper(candidates,i,target-candidates[i],lst,res)
                lst.pop()

leetcode 40 Combination Sum II

Question

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:
All numbers (including target) will be positive integers.
Elements in a combination (a1, a2, … , ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
The solution set must not contain duplicate combinations.

Solution

The only difference from above is that every time it begins at the next point.

class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        self.helper(candidates,target,0,[],res)
        return res

    def helper(self,candidates,target,start,lst,res):
        if target <= 0:
            if target == 0:
                res.append(list(lst))
            return
        for i in xrange(start,len(candidates)):
            if i == start or candidates[i] != candidates[i-1]:
                lst.append(candidates[i])
                self.helper(candidates,target-candidates[i],i+1,lst,res)
                lst.pop()

leetcode 216 Combination Sum III

Question

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

Solution

Same to above.

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        res = []
        self.helper(k,n,1,[],res)
        return res

    def helper(self,k,n,start,lst,res):
        if k == 0 or n <= 0:
            if k == 0 and n == 0:
                res.append(list(lst))
            return
        for i in xrange(start,10):
            lst.append(i)
            self.helper(k-1,n-i,i+1,lst,res)
            lst.pop()