组合总和变体

组合总和（LeetCode 39）

数组元素可重复使用，找所有和为 target 的组合。

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

private void backtrack(int[] cands, int target, int start,
                        int sum, List<Integer> path, List<List<Integer>> res) {
    if (sum == target) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < cands.length; i++) {
        if (sum + cands[i] > target) break;   // 剪枝（已排序）
        path.add(cands[i]);
        backtrack(cands, target, i, sum + cands[i], path, res);   // i（可重复）
        path.removeLast();
    }
}

组合总和 II（LeetCode 40）

每个元素只能用一次，但数组有重复，需去重。

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

private void backtrack(int[] cands, int target, int start,
                        int sum, List<Integer> path, List<List<Integer>> res) {
    if (sum == target) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < cands.length; i++) {
        if (sum + cands[i] > target) break;
        // 同一层跳过重复
        if (i > start && cands[i] == cands[i-1]) continue;
        path.add(cands[i]);
        backtrack(cands, target, i + 1, sum + cands[i], path, res);
        path.removeLast();
    }
}

去重关键：i > start（同层才去重，不同层允许相同值）。

组合总和 III（LeetCode 216）

从 1~9 中选 k 个不重复数字，和为 n。

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(k, n, 1, 0, new ArrayList<>(), res);
    return res;
}

private void backtrack(int k, int n, int start,
                        int sum, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        if (sum == n) res.add(new ArrayList<>(path));
        return;
    }
    for (int i = start; i <= 9; i++) {
        if (sum + i > n) break;
        path.add(i);
        backtrack(k, n, i + 1, sum + i, path, res);
        path.removeLast();
    }
}

目标和（LeetCode 494）

给数组每个元素加 + 或 - 号，计算结果为 target 的方案数。

回溯（理解直观）

public int findTargetSumWays(int[] nums, int target) {
    return dfs(nums, target, 0, 0);
}

private int dfs(int[] nums, int target, int i, int sum) {
    if (i == nums.length) return sum == target ? 1 : 0;
    return dfs(nums, target, i + 1, sum + nums[i])
         + dfs(nums, target, i + 1, sum - nums[i]);
}

DP 优化（0-1 背包，O(n·sum)）

设 P 为正号集合，N 为负号集合：

• sum(P) - sum(N) = target
• sum(P) + sum(N) = total
• 解得 sum(P) = (target + total) / 2

转化为找子集和为 (target+total)/2 的方案数：

public int findTargetSumWays(int[] nums, int target) {
    int total = Arrays.stream(nums).sum();
    if (Math.abs(target) > total || (target + total) % 2 != 0) return 0;
    int bag = (target + total) / 2;
    int[] dp = new int[bag + 1];
    dp[0] = 1;
    for (int x : nums)
        for (int j = bag; j >= x; j--)
            dp[j] += dp[j - x];
    return dp[bag];
}

总结