题目描述

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

• 所有数字（包括目标数）都是正整数。
• 解集不能包含重复的组合。 

样例

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

算法分析

dfs + 排序

• 1、为了避免选择了重复的元素，先对数组有规则的进行排序，例如从小到大排序
• 2、当枚举到某一位置时，找到相同的元素区间[u,k - 1]，共cnt个可以选，暴力枚举每个数字选多少个
• 3、当枚举到的总值sum > target，表示该枚举方式不合法，直接return
• 4、当枚举完每个数字之后，若sum == target，表示该选择方案是合法的，记录该方案

注意:枚举的时候的小细节，枚举每个数字选多少个的时候，本来是枚举多少个，最后dfs下一层完后，就应该全部恢复现场，删除多少个，再枚举下一种情况。可以直接枚举该数字选多少个，假设最多能选t个，则每选一个dfs一次，操作了t + 1次之后，再把这t个相同的数字一次性恢复现场 (y总的小技巧)

时间复杂度

不好分析

参考文献

Java 代码

class Solution {
    static List<List<Integer>> ans = new ArrayList<List<Integer>>();
    static void dfs(int[] candidates,int target,int u,int sum,List<Integer> t)
    {
        if(sum > target) return ;
        if(u == candidates.length)
        {
            if(sum == target) ans.add(new ArrayList<Integer>(t));
            return ;
        }
        int k = u;
        while(k < candidates.length && candidates[k] == candidates[u]) k ++;
        int cnt = k - u;//该数字个数
        for(int i = 0;sum + candidates[u] * i <= target && i <= cnt;i ++)
        {
            dfs(candidates,target,k,sum + candidates[u] * i,t);//注意这里是要跳到k
            t.add(candidates[u]);
        }

        for(int i = 0;sum + candidates[u] * i <= target && i <= cnt;i ++)
            t.remove(t.size() - 1);
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        ans.clear();
        List<Integer> t = new ArrayList<Integer>();
        dfs(candidates,target,0,0,t);
        return ans;
    }
}