39. 组合总和

1. 题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

2. 思路

  • 已知题目要求组合出一个目标数组，以实现目标数组的元素总和达到目标和，同时源数组中的元素可以被重复使用
  • 解题采用回溯算法，回溯模板为以下：
1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}
  • 需要额外注意的是，本题的源数组在回溯前进行从小到大排序可以很好地提高时间效率，同时可以在后续回溯的过程中方便进行剪枝
  • 回溯方法中，参数分别是源数组、目标和、临时数组、当前临时数组的总和、起始遍历下标，其中终止条件为当前临时数组的总和 >= 目标和，同时当当前临时数组的总和 == 目标和时，将临时数组记入结果集并返回
  • for层循环中，起始下标采用参数传入的起始遍历下标，同时遍历的元素必须小于等于当前临时数组的总和 - 目标和（由于元素已有序，因此此处可以达成剪枝，防止出现重复结果），遍历的过程中，将元素添加进临时数组中，并进行二次回溯，回溯完成后，将结果进行撤销（撤销过程即是移除数组最后一个元素）
  • 完成以上回溯后，将结果集进行返回

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private List<List<Integer>> result = new ArrayList<>();

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

    private void helper(int[] candidates, int target, List<Integer> list, int currentSum, int startIndex) {
        if (currentSum >= target) {
            if (currentSum == target) {
                result.add(new ArrayList<Integer>(list));
            }
            return;
        }

        var diff = target - currentSum;

        for (var i = startIndex; i < candidates.length && candidates[i] <= diff; ++i) {
            var candidate = candidates[i];
            list.add(candidate);
            helper(candidates, target, list, currentSum + candidate, i);
            list.remove(list.size() - 1);
        }
    }
}

4. 复杂度

  • 时间复杂度: O(2^n)，每个决策点都面临2个选择：选择当前元素和不选择当前元素，因此对于一个长度为n的数组，每个位置都会有两种可能的状态，因此对于整个源数组的所有可能组合，则会有2^n种可能
  • 空间复杂度: O(n)，其中n为递归调用所需要的栈空间

image-20231227110043774