Leetcode 40 组合总和II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

public class Solution {
    private IList<IList<int>> res = new List<IList<int>>();
    private int[] candidates;
    private int target;
    private int len;
    private List<int> newCandidates;

    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        this.newCandidates = new List<int>(candidates);
        this.target = target;
        this.len = newCandidates.Count;
        //在这先排序
        newCandidates.Sort();

        DFS(0, new List<int>(), 0);
        return res;
    }

    private void DFS(int start, List<int> path, int sum){
        if(sum >= target){
            if(sum == target){
                List<int> temp = new List<int>(path); //直接赋值就是空的
                res.Add(temp);
            }
            return;
        }else{
            //还小于target
            for(int i = start; i<len; i++){
                
                //同一层相同的数就不用遍历了
                //这里如果为[10,1,2,7,6,1,5]，里面有2个1.在第一层遍历过1后，就可以不用遍历了
                if(i > start && newCandidates[i] == newCandidates[i-1]){
                    continue;
                }
                path.Add(newCandidates[i]); //加入到数组中
                //与39题不一样的在这。
                //在本层遍历过这个数了。如果下一层dfs。依然以i开始。那么还是会遍历到这点。也就是重复了。
                //所以在这加个1，就不会重复
                DFS(i+1, path, sum+newCandidates[i]);
                path.RemoveAt(path.Count-1); //然后退出来（回溯）
            }
        }
    }
}