LeetCode 组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
示例 1：

输入：candidates = [2,3,6,7], target = 7,
所求解集为：
[
[7],
[2,2,3]
]
示例 2：

输入：candidates = [2,3,5], target = 8,
所求解集为：
[
[2,2,2,2],
[2,3,3],
[3,5]
]

提示：

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
candidate 中的每个元素都是独一无二的。
1 <= target <= 500

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> subList = new ArrayList<Integer>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,0,0,target);
        return list;
    }
    public void dfs(int[] candidates,int x,int step,int target){
        /*
        如果没有对数组进行排序，并且下面的for循环中没有判断target - candidates[i] < 0这一步的时候
        那么就需要有这一步。因为存在[2,7,6,3,5,1],target = 9的例子，如果下面的for循环中有if判断，
        但是没有对数组进行排序的时候，那么就会发生报错，因为根据代码，就会发现缺少了诸如[2,6,1]这
        样的结果，错误原因就在于没有在对数组进行排序的时候，就利用target - candidates[i]是否小于0
        来判断是否可以结束程序，返回到上一层递归中
        if(target < 0)
            return;
       */
        if(target == 0){
            //当target  == 0的时候，说明subList满足和为target
            list.add(new ArrayList<Integer>(subList));
            return;
        }
        int i;
        for(i = x; i < candidates.length; i++){
            /*
            如果减去candidates[i]之后小于0，由于数组升序排序的，后面的数只会比candidates[i]大，所
            直接返回所以,如果没有这一步进行判断的话，那么可以不进行排序，只是进行循环之前判断
            target是否小于0，如果是，直接返回
            */
            if(target - candidates[i] < 0) 
               return; 
            subList.add(candidates[i]);
            dfs(candidates,i,step + 1,target - candidates[i]);//由于一个数字可以重复使用，所以下次递归的时候，依旧是从i下标开始的
            subList.remove(step);
        }
    }
}

运行结果:

LeetCode 组合总和II

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

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

注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii

class Solution {
    List<List<Integer>> list = new ArrayList<List<Integer>>();
    List<Integer> subList = new ArrayList<Integer>();
    int result;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,0,0,target);
        return list;
    }
    public void dfs(int[] candidates,int x,int step,int target){
            //step用于删除列表的最后一个元素
            if(result == target){
                list.add(new ArrayList<Integer>(subList));  
                return; 
            }
            int i;
            /*
            这是正常的深度优先搜索的情况，每一次都是从下标为0开始遍历，为了标记哪些元素已经访问
            过了，所以定义一个boolean数组，在判断是否可以放入到列表的时候，需要判断当前下标i已经
            被访问过了，或者虽然下标i对应的数没有被访问过，但是前一个数字 i - 1对应的数字
            candidates[ i - 1] == candidates[i]，并且visited[i - 1]重新置为了false，说明此时
            candidates[i]已经将值为candidates[i]的所有情况都枚举了，所以利用continue结束本次循
            环。
            
            但是这样提交之后，就会发现会有错误，例如[1,1,2,5,7]，target = 7，那么这样每次递归都是
            从0开始，从而导致了会出现重复的例子，例如[1,2,5],[1,5,2]，这并不是会因为数组已经排序
            了就可以避免重复的。因此，解决的办法是在将当前i放入到列表之后，下一个放入到列表中的元
            素是在i后面，也即dfs(candidates,i + 1,step + 1,target)，并且for循环中i初始值是形式参
            数x
            也正因如此，每次递归的时候访问到的元素都是没有访问过的，所以if判断也就没有必要写上
            visited[i]了.同时由于我们没有在if判断中写上visited[i]这一个判断，所以表明了visited
            的值对我们程序来说并没有什么实际意义，所以不需要对其进行赋值，之后再重置，所以也就影响
            到了i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1]，所以整个if判断
            就变成了if(i > x && candidates[i] == candidates[i - 1])
            for(i = 0; i < candidates.length; i++){
                if(visited[i] || i > 0 && candidates[i] == candidates[i - 1] && !visited[i - 1])
                   continue;
                if(result + candidates[i] > target)
                   return;
                subList.add(candidates[i]);
                result += candidates[i];
                visited[i] = true;
                dfs(candidates,i + 1,step + 1,target);
                subList.remove(step);
                visited[i] = false;
                result -= candidates[i];
            }
            */
            for(i = x; i < candidates.length; i++){
            /*
            由于数组存在重复元素的情况，所以在将数组排序之后，如果当前下标i的数和i - 1对应的值
            相等，那么下标为i - 1的数已经将下标为i的所有情况都考虑了，所以利用continue结束本次循环
            所以判断的条件是i > x && candidates[i] == candidates[i - 1]。这样也可以理解为
            candidates[i]和candidates[i - 1]对应的target相等的时候，candidates[i - 1]已经将
            candidates[i]的所有情况都考虑了，所以就没有必要再进行枚举candidates[i - 1]了
            */
                if(i > x && candidates[i] == candidates[i - 1])
                   continue;
                  /*
                  如果当前的result + candidates[i] 大于了target,由于candidates数组已经排序了，那
                  么i后面的值一定大于candidates[i]，所以result加上后面的值也会大于target，所以就
                  没有必要再递归下去了，直接返回到上一层递归。
                  */
                if(result + candidates[i] > target)
                   return;
                subList.add(candidates[i]);
                result += candidates[i];
                dfs(candidates,i + 1,step + 1,target);
                subList.remove(step);
                result -= candidates[i];
            }
    }
}

运行结果: