Leetcode(39) Combination Sum

发表于 | 分类于

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.

Example 1:

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

Example 2:

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

解法

最开始想用动态规划来解这道题，但因为要输出是哪些数组成的答案，故不太方便。采用深度优先搜索的一般方法即可解题。为了进行剪枝，需对数组进行从大到小排序，如果碰到比target值大的，那么显然之后的数都不需要进行搜索了。同时，需要注意重复查找的问题，比如 input:[2,3,6,7] 7时，可能出现[[2,2,3],[2,3,2],[3,2,2],[7]]的情况，为了解决重复，需要让搜索时按一定的顺序进行，此题的解决方案是下一个加入序列搜索的数一定大于等于当前搜索的数，引入start参数，这样就保证了结果的唯一性。

具体代码如下：

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
class Solution {
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, target, tmp, 0);
        return res;
    }

    void helper(int[] candidates, int target, List<Integer> tmp, int start) {
        if (target == 0) {
            res.add(new ArrayList<>(tmp));
            return;
        } else if (target < 0) {
            return;
        } else {
            for (int i = start; i < candidates.length && target >= candidates[i]; i++) {
                target = target - candidates[i];
                tmp.add(candidates[i]);
                helper(candidates, target, tmp, i);
                target = target + candidates[i];
                tmp.remove(tmp.size() - 1);
            }
        }

    }
}