【Leetcode 39】组合总和 —— 回溯法

39. 组合总和

给你一个无重复元素的整数数组candidates和一个目标整数target ，找出candidates中可以使数字和为目标数target的 所有不同组合，并以列表形式返回。你可以按**任意顺序 **返回这些组合。

candidates中的同一个数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为target的不同组合数少于150个。

示例 1：

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

题目分析

回溯法解题步骤

1. 针对所给问题，定义问题的解空间
2. 确定易于搜索的解空间结构
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索

回溯法有“通用解题法”之称，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。
详细可见 Leetcode 回溯法详解

经典排列树，按节点遍历，更多案例可见 Leetcode 回溯法详解

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, 0, new ArrayList<>(), target);
        return res;
    }

    /**
     * output(x)     记录或输出得到的可行解x
     * constraint(t) 当前结点的约束函数
     * bount(t)      当前结点的限界函数
     * @param t  t为当前解空间的层数
     */
    private void backtrack(int[] nums, int k, List<Integer> temp, int target) {
        // bount
        if (target == 0) {
            res.add(new ArrayList<>(temp));
            return;
        } else if (target < 0) {
            return;
        }

        for (int i = k; i < nums.length; ++i) {
            // 剪枝
            if (target - nums[i] < 0) {
                break;
            }
            temp.add(nums[i]);
            backtrack(nums, i, temp, target - nums[i]);
            temp.remove(temp.size() - 1);
        }
    }
}