LeetCode39题： 组合总和（原创）

【题目描述】

        给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 ：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：

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

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

【解题代码】

package dp;

import java.util.*;

public class CombinationSum {

    public static void main(String[] args) {
        //int[] candidates = {2, 3, 6, 7};
        int[] candidates = {1, 2, 3};
       
        System.out.println("开始计算。。。");
        long start = System.currentTimeMillis();
        List<List<Integer>> numLists = new CombinationSum().combinationSum(candidates, 4);
        System.out.println("运行时长：" + (System.currentTimeMillis() - start) + "ms");
        for (List<Integer> numList : numLists) {
            System.out.println(Arrays.toString(numList.toArray()));
        }
    }

    private List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> numLists = new ArrayList<>();
        List<Integer> numList = new ArrayList<>();
        doCombinationSum(candidates, 0, target, numList, numLists);
        return numLists;
    }

    private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists) {
        if (target == 0) {
            numLists.add(new ArrayList<>(numList));
        } else if (n < candidates.length) {
            doCombinationSum(candidates, n + 1, target, numList, numLists);
            if (target >= candidates[n]) {
                numList.add(candidates[n]);
                doCombinationSum(candidates, n, target - candidates[n], numList, numLists);
                numList.remove(numList.size() - 1);
            }
        }
    }

}

【解题思路】

        看到此题描述，第一反应就是应该采用“回溯算法”：依次遍历数组candidates 里面数字，根据题意对当前索引i的数字做两种选择：

1. 当前数字candidates[i]不加入候选队列：直接递归处理下一个索引数字i+1；
2. 当前数字candidates[i]如果小于target，选择将其加入候选队列：将目标整数 target减去当前candidates[i]，因为数字可以重复选择，再次递归处理索引数字i；
3. 目标整数 target为0,说明当前候选数字序列满足要求，添加到结果集，此趟递归结束
4. 按照上述思路完成代码编写，提交LeetCode成功

【解题步骤】

1. 定义一个回溯递归函数doCombinationSum，参数包括整数数组 candidates，当前索引值n,目标值target,当前候选数列numList，结果数列numLists：

   private void doCombinationSum(int[] candidates, int n, int target, List<Integer> numList, List<List<Integer>> numLists)

2. 如果目标值target为0，说明当前候选数字序列numList满足要求，添加到结果集numLists

   if (target == 0) {
       numLists.add(new ArrayList<>(numList));
   } 

3. 如果数组遍历还没遍历完，首先选择不选择当前数字，直接递归处理下一个索引数字即可

   } else if (n < candidates.length) {
       doCombinationSum(candidates, n + 1, target, numList, numLists);

4. 接下来，如果当前数字小于等于目标值target，那么选择此数字，将此数字添加到候选数字序列，将目标值target去当前candidates[i]，并从当前索引重复递归，递归完毕，回溯将次数字从候选数字序列中删除

   if (target >= candidates[n]) {
       numList.add(candidates[n]);
       doCombinationSum(candidates, n, target - candidates[n], numList, numLists);                
       numList.remove(numList.size() - 1);
   }

【思考总结】

1. 了解掌握回溯算法定义：回溯算法定义 回溯算法，是一种选优搜索法，又称为试探法，按选优条件向前搜索以达到目标。 回溯算法简要说：但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。 而满足回溯条件的某个状态的点称为“回溯点”。
2. 回溯与递归的区别：递归的基本性质就是函数调用，在处理问题的时候，递归往往是把一个大规模的问题不断地变小然后进行推导的过程。 回溯则是利用递归的性质，从问题的起始点出发，不断地进行尝试，回头一步甚至多步再做选择，直到最终抵达终点的过程；
3. LeetCode解题之前，一定不要看题解，看了就“破功”了！