组合总和

以你之姓@ 2022-12-04 09:19 167阅读 0赞

# 组合总和 #

## 1、预备知识：数组的组合 ##

### 1.1、题目要求 ###

求数组的组合，比如数组 `[1, 2, 3]` 的组合为：

[
    	[1, 1, 1],
    	[1, 1, 2],
    	[1, 1, 3],
    	[1, 2, 2],
    	[1, 2, 3],
    	[1, 3, 3],
    	[2, 2, 2],
    	[2, 2, 3],
    	[2, 3, 3],
    	[3, 3, 3],
    ]

### 1.2、代码思路 ###

组合必递归：我们想想求组合的思路是啥？

1.  比如说我们要求数组 `nums = [1, 2, 3]` 的组合，首先以元素 `1` 打头，然后在数组 `nums` 中递归地寻找长度为 `2` 的组合
2.  第二步我们以元素 `2` 打头，在数组中递归地寻找长度为 `2` 的组合，这里需要注意一个问题，在组合中 `[1, 2]` 和 `[2, 1]` 为相同的组合，所以当我们以 `2` 打头的时候，就不应该在考虑元素 `1`，所以我们需要在子数组 `[2, 3]` 中寻找全排列，解决办法：我们需要在递归函数的参数中添加一个 `start` 变量，用于当前打头元素的起始索引
3.  第三步我们以元素 `3` 打头，在子数组 `[3]` 中递归地寻找长度为 `2` 的组合

--------------------

代码实现细节说明：

1.  递归函数 `void dfs(int[] nums, List<Integer> path, int start) {` 参数说明：我们使用 `List<Integer> path` 来记录递归的路径(即组合的结果)，使用 `start` 记录当前打头元素的起始索引
2.  在整个递归函数中，我们需要使用 `for` 循环遍历数组中每个元素，并以当前元素打头，递归地在子数组中寻找组合的路径，直到 `path.size() == nums.length`
3.  当 `path.size() == nums.length` 时，说明路径的长度与原数组的长度相同，证明已经递归至深层，也即我们找到一条组合路径，将其添加至结果集中
4.  在进行递归之前，我们将当前元素添加至路径 `path` 之中，在递归回溯之后，我们将当前元素从路径 `path` 中移除

--------------------

多句嘴

我怎么感觉我这里的设计思路有种函数调用时保护现场的味道

### 1.3、代码实现 ###

代码

class Solution {
        
        List<List<Integer>> combination = new ArrayList<>();
    
        public List<List<Integer>> combination(int[] nums) {
        
            dfs(nums, new ArrayList<>(nums.length), 0);
            return combination;
        }
    
        // 求数组的组合
        public void dfs(int[] nums, List<Integer> path, int start) {
        
            // 如果路径的长度与原数组的长度相同，则证明找到了一种组合结果，将其添加至结果集并回溯
            if (path.size() == nums.length) {
        
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < path.size(); i++) {
        
                    list.add(path.get(i));
                }
                combination.add(list);
                return;
            }
    
            // 遍历数组每个元素，以 nums[i] 打头，求子数组 [start, nums] 的组合
            for (int i = start; i < nums.length; i++) {
        
                path.add(nums[i]); // 递归之前，我们将当前元素添加至路径 path 之中
                dfs(nums, path, i); // 在 [i, nums] 之间，递归计算组合
                path.remove(path.size() - 1); // 递归回溯之后，我们将当前元素从路径 path 中移除
            }
        }
    
    }

## 2、组合总和 ##

### 2.1、参考资料 ###

https://leetcode-cn.com/problems/combination-sum/

### 2.2、题目要求 ###

> **题目描述**

给定一个**无重复元素**的数组 `candidates` 和一个目标数 `target` ，找出 `candidates` 中所有可以使数字和为 `target` 的组合。

`candidates` 中的数字可以无限制重复被选取。

> **说明：**

1.  所有数字（包括 `target`）都是正整数。
2.  解集不能包含重复的组合。

> **示例 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]
    ]

### 2.3、代码思路 ###

这道题很像求【数组的组合】，但是又有一丁点不同，当然递归是肯定逃不了的

1.  因为需要组合之和等于目标值 `target`，但至于需要多少个元素相加才能等于 `target`，我们并不知道，这一点和【数组的组合】不同，所以递归条件需要改变
2.  因为需要记录组合之和是否等于 `target`，我们换个思路思考，每次进入递归时，让 `target` 减去当前元素的值，当 `target == 0` 时，则证明找到目标路径，将当前组合结果添加至结果集中，然后 `return`，进行回溯
3.  那么要是 `target` 一直不可能等于 `0` 怎么办？递归不就成了个无底洞吗？题目中还有个条件：所有数字（包括 `target`）都是正整数。当我们发现 `target` 是负数时，则证明此条路径不可能使得组合之和等于 `target`，直接 `return` 进行回溯即可
4.  和【数组的组合】一样，我们需要 `List<Integer> path` 来记录递归的路径(即组合的结果)，`start` 记录当前打头元素的起始索引

### 2.4、代码实现 ###

代码

class Solution {
        
        List<List<Integer>> combinationSum = new ArrayList<>();
    
        public List<List<Integer>> combinationSum(int[] nums, int target) {
        
            dfs(nums, target, new ArrayList<>(), 0);
            return combinationSum;
        }
    
        // 求数组元素的组合之和是否等于 target
        public void dfs(int[] nums, int target, List<Integer> path, int start) {
        
            // 如果小于 target < 0，证明此条路径不可能使得组合之和等于 target，直接 return，进行回溯
            if(target < 0){
        
                return;
            }
    
            // 如果 target == 0，证明找到目标路径，将当前组合结果添加至结果集中，然后 return，进行回溯
            if (target == 0) {
        
                List<Integer> list = new ArrayList<>();
                for (int i = 0; i < path.size(); i++) {
        
                    list.add(path.get(i));
                }
                combinationSum.add(list);
                return;
            }
    
            // 遍历数组每个元素，以 nums[i] 打头，
            for (int i = start; i < nums.length; i++) {
        
                target -= nums[i]; // 递归之前，目标值减去当前元素的值，即为下一次的目标值
                path.add(nums[i]); // 递归之前，我们将当前元素添加至路径 path 之中
                dfs(nums, target, path, i); // 递归地寻找组合之和是否等于 target
                target += nums[i]; // 递归回溯之后，我们恢复 target 的值
                path.remove(path.size() - 1); // 递归回溯之后，我们将当前元素从路径 path 中移除
            }
        }
    }