39.组合总和

给定一个无重复元素的数组 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中的[2,2,3]和[2,3,2]）

方法二

动态规划求解

这里采用了方法一

public class CombinationSum {
    int[] candidates;
    int target;
    List<List<Integer>> mList = new ArrayList<>();

    public static void main(String[] args) {
        int[] arr = {2, 3, 5};
        int tar = 8;
        CombinationSum combinationSum = new CombinationSum();
        combinationSum.combinationSum(arr, tar);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        this.candidates = candidates;
        this.target = target;
        find(new ArrayList<>(), target);
        //System.out.println(mList);
        return mList;
    }

    public void find(List<Integer> list, int num) {
        if (num < 0) {
            return;
        }
        //遍历递归
        for (int candidate : candidates) {
            //如果这次选的数比前面已经选了的数还要小，那么直接跳过
            //这样等于剪枝工作，去掉可能重复的list
            if (!list.isEmpty() && candidate < list.get(list.size() - 1)) {
                continue;
            }
            List<Integer> list1 = new ArrayList<>(list);
            list1.add(candidate);
            int res = num - candidate;
            //res为0，代表list1中所有数的和等于target
            //res小于0，则代表这条递归路径行不通
            if (res == 0) {
                mList.add(list1);
            } else if (res > 0) {
                find(list1, res);
            }
        }
    }
}