By yusijia

Updated:

Contents

/*

  • 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.
  • For example, given candidate set 10,1,2,7,6,1,5 and target 8,
  • A solution set is:
  • [1, 7]
  • [1, 2, 5]
  • [2, 6]
  • [1, 1, 6]
    */
  • 用了下HashSet水过去…
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
36
37
38
39
40
41
42
43
44
45
public class Solution {

    /**
     * @param candidates 题目给的数组
     * @param target 目标数
     * @return
     */
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if(candidates == null || candidates.length == 0){
            return new ArrayList<List<Integer>>();
        }
        
        Set<List<Integer> > result = new HashSet<List<Integer> >();
        List<Integer> single = new ArrayList<Integer>();
        Arrays.sort(candidates);
        dfs(result, single, candidates, 0, target);
        //将Set转换为ArrayList返回
        return new ArrayList<List<Integer>>(result);
    }
    
    /**
     * 
     * @param result 存总结果
     * @param single 存临时数据
     * @param candidates 题目给的数组
     * @param i 当前选到数组的第i位
     * @param target 题目给的目标数和single中总和的差值
     */
    private void dfs(Set<List<Integer> > result, List<Integer> single, int[] candidates, int i, int target) {
        if (target == 0) {
            result.add(new ArrayList<Integer>(single));
            return ;
        }
        
        for(int j = i; j < candidates.length; j++){
            // 如果小于就返回，表明此后不会有解了
            if (candidates[j] > target) {
                return;
            }
            single.add(candidates[j]);
            dfs(result, single, candidates, j + 1, target - candidates[j]);
            single.remove(single.size() - 1);
        }
    }
}
  • 加去重处理
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
public class CombinationSumII {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        dfs(res, list, num, 0, 0, target);
        return res;
    }

    public void dfs(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> list,
            int[] num, int pos, int sum, int target) {
        if(sum == target)
            res.add(new ArrayList<Integer>(list));
        if(sum < target) {
            for(int i = pos; i < num.length; i++) {
                // 回溯的时候去重
                if(i > pos && num[i] == num[i - 1])
                    continue;
                list.add(num[i]);
                dfs(res, list, num, i + 1, sum + num[i], target);
                list.remove(list.size() - 1);
            }
        }
    }
}
  • C++版本
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
class Solution {  
private:  
    void dfs(vector<vector<int> > &ans, vector<int> &single,  
            vector<int> &candi, int cur, int rest) {  
        int sz = candi.size();  
        if (rest == 0) {  
            // 这里加去重处理
            // 例如[1, 1, 1, 2, 2], target = 5, 这里cur是为了取最右边的2
            if (!single.empty() && cur < sz && single[single.size() - 1] == candi[cur])  
                return;  
            ans.push_back(single);  
            return;  
        }  

        if (sz <= cur || rest < 0)  
            return;  
        single.push_back(candi[cur]);  
        dfs(ans, single, candi, cur + 1, rest - candi[cur]);  
        single.pop_back();
        //这里加去重处理
        // 例如[1, 1, 1, 2], target = 3, 这里cur是为了取最右边的1
        if (!single.empty() && single[single.size() - 1] == candi[cur])  
            return;  
        dfs(ans, single, candi, cur + 1, rest);
    }  
public:  
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {  
        vector<vector<int> > ans;  
        vector<int> single;  
        sort(num.begin(), num.end());  
        dfs(ans, single, num, 0, target);  
        return ans;  
    }  
};
Contents