Problem description:

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

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

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

1
2
3
4
5
6
7
8
Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

1
2
3
4
5
6
7
8
9
Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

Solution:

DFS + backtracking.
In backtrack(), I use the following 5 inputs.

  • vector<vector>& res, store every combination here
  • vector& temp, this is buffer for recursive, add/remove element depends on depth of dfs
  • vector& candidates,
  • int remain, what we targeting, need to input remain-i when dfs into next level
  • int start, this is because we can not have duplicate sets, to record what elements we already passed or visited.

Time complexity: O(n*2^n)
The number of recursive calls, T(n) satisfies the recurrence T(n) = T(n - 1) + T(n - 2) + … + T(1) + T(0),which solves to T(n) = O(2^n). Since we spend O(n) time within a call, the time complexity is O(n2^n);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def dfs(res, tmp, candidates, target):
            if target < 0:
                return 
            elif target == 0:
                res.append(tmp)
            else:
                for i in range(len(candidates)):
                    dfs(res, tmp+ [candidates[i]], candidates[i:], target-candidates[i])
                    
        res = []
        dfs(res, [], candidates, target)
        return res
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
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        sort(candidates.begin(), candidates.end());
        vector<int> tmp;
        backtrack(res, tmp, candidates, target, 0);
        return res;
    }
    
private :
    void backtrack(vector<vector<int>>& res, vector<int>& temp, vector<int>& candidates, int remain, int start){
        if(remain < 0) return; //did not match the target
        else if(remain == 0) res.push_back(temp); //put into the result
        else{
            for(int i = start; i< candidates.size(); i++){
                //search candidate[i] have any combanition
                temp.push_back(candidates[i]); 
                backtrack(res, temp, candidates, remain-candidates[i], i); 
                
                temp.resize(temp.size()-1);
            }
        }
    }

};

reference:
https://goo.gl/HkoJaT
https://goo.gl/XX6WAv
http://www.1point3acres.com/bbs/thread-117602-1-1.html