数组中和为定值的子集

题目具体是这样的，给定n个数字，比如{2,6,1,7,4,9}，并给定一个SUM，比如SUM=20，在上述这6个数字中，挑出一些，使得他们的和等于SUM，把所有的组合都找出来。我们这个例子的结果就是：
1 + 2 + 4 + 6 + 7 = 20
1 + 4 + 6 + 9 = 20
4 + 7 + 9 = 20
 

组合总和 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]
]

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Test40 {
    public static void main(String[] args) {
        int[] candidates = {2,6,1,7,4,9};
        System.out.println(combinationSum2(candidates,20));
    }
    static List<List<Integer>> lists = new ArrayList<>();

    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        //对数组进行排序   这个很关键
        if (candidates == null || candidates.length == 0 || target < 0) {
            return lists;
        }
        List<Integer> list = new ArrayList<>();
        dfs(list, candidates, target, 0);
        return lists;
    }

    private static void dfs(List<Integer> list, int[] candidates, int target, int start) {
        //递归的终止条件
        if (target < 0) {
            return;
        }
        if (target == 0) {
            lists.add(new ArrayList<>(list));
        } else {
            for (int i = start; i < candidates.length; i++) {
                //因为这个数和上个数相同，所以从这个数开始的所有情况，在上个数里面都考虑过了，需要跳过
                if (i != start && candidates[i] == candidates[i - 1]) {
                    continue;
                }
                list.add(candidates[i]);
                dfs(list, candidates, target - candidates[i], i + 1);
                list.remove(list.size() - 1);
                //归去来兮
            }
        }
    }
}

思路

 

以{1, 1, 2, 5, 6, 7}，target = 8 为例模拟一下解题流程
首先排个序，是为了以后能方便的剪枝以及跳过重复的解

遍历数组，进行累加，若小于 8 就继续遍历，得到 [1, 1, 2]
下一个 5 添加进来后就大于 8 了，所以直接 break 这次遍历，并从列表中退出 2，然后从2的下一个元素继续遍历，得到 [1, 1, 5]
下一个 6 添加进来后大于 8，所以去掉 5，从将5 后一个元素继续得到 [1, 1, 6]，判断等于 8，所以保存该解，因为已经排好了序，所以后面的元素不用再看了，就 break这次循环
这时列表中只有 [1, 1]， 将第二个 1 退出，从它的后一个元素开始遍历，得到 [1, 2, 5]，保存该解并break这次循环
退出2，从它的下一个元素开始，得到[1, 5]
下一个 6 添加进来后大于 8，所以去掉5，添加6，得到[1, 6]
下一个 7 添加进来后大于 8，所以去掉6，添加7，得到[1, 7]，保存该解并break这次循环
退出1，从它下一个元素开始，因为下一个元素还是1，所以跳过它，再下一个元素是2，于是从2开始得到[2, 5]
下一个 6 添加进来后大于 8，所以去掉5，添加6，得到[2, 6]，保存该解并break这次循环
退出2，从它下一个元素 5 开始，得到 [5]
下一个 6 添加进来后大于 8，所以去掉5，添加6，得到 [6]
下一个 7 添加进来后大于 8，所以去掉6，添加7，得到 [7]

组合总和2 

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

candidates 中的数字可以无限制重复被选取。

说明：

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

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]
/*
 * @Author liuhaidong
 * @Description 该程序的思路
 * 2 2 2 2
 * 2 2 2
 * 2 2 3
 *
 * @Date 15:51 2019/9/25 0025
 **/
static List<List<Integer>> lists = new ArrayList<>();
//这个list存放所有数组
public static List<List<Integer>> combinationSum(int[] candidates, int target) {
    if (candidates == null || candidates.length == 0 || target < 0) {
        return lists;
    }
    List<Integer> list = new ArrayList<>();
    dfs(list,candidates,target,0);
    //第一个list存放小数组，
    return lists;
}
 
private static void dfs(List<Integer> list, int[] candidates,int target,int start){
    //递归的终止条件
    if(target < 0){
        return;
    }
    if(target == 0){
        lists.add(new ArrayList<>(list));
    }else {
        for (int i=start;i<candidates.length;i++){
            list.add(candidates[i]);
            //*********************************************************
            //因为每个数字都可以使用无数次，所以递归还可以从当前元素开始
            //*********************************************************
            dfs(list,candidates,target-candidates[i],i);
            list.remove(list.size()-1);
        }
    }