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 。仅有这两种组合。

样例 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

分析：

面对这道算法题目，二当家的陷入了沉思。
遍历或者递归，递归比较直观，深度优先，回溯。
题目要求所有可能的组合，不能重复，本来是需要想办法去重的，但是题目规定参数中所有元素互不相同，那我们只要选择不同下标的组合就相当于选择了不同元素的组合。

题解：

rust

impl Solution {pub fn combination_sum(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {fn dfs(candidates: &Vec<i32>, target: i32, idx: usize, row: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {if idx == candidates.len() {// 尝试到底，开始回溯return;}if target == 0 {// 符合条件的一个组合ans.push(row.clone());return;}if target >= candidates[idx] {// 选择当前下标数字row.push(candidates[idx]);dfs(candidates, target - candidates[idx], idx, row, ans);row.pop();}// 跳过当前下标数字dfs(candidates, target, idx + 1, row, ans);}let mut ans = Vec::new();dfs(&candidates, target, 0, &mut Vec::new(), &mut ans);return ans;}
}

go

func combinationSum(candidates []int, target int) [][]int {var ans [][]intvar dfs func(int, int, []int)dfs = func(target int, idx int, row []int) {if idx == len(candidates) {// 尝试到底，开始回溯return}if target == 0 {// 符合条件的一个组合ans = append(ans, append([]int{}, row...))return}// 选择当前下标数字if target >= candidates[idx] {row = append(row, candidates[idx])dfs(target-candidates[idx], idx, row)row = row[:len(row)-1]}// 跳过当前下标数字dfs(target, idx+1, row)}dfs(target, 0, []int{})return ans
}

c++

class Solution {
private:void dfs(vector<int>& candidates, int target, int idx, vector<int>& row, vector<vector<int>>& ans) {if (idx == candidates.size()) {// 尝试到底，开始回溯return;}if (target == 0) {// 符合条件的一个组合ans.emplace_back(row);return;}// 选择当前下标数字if (target >= candidates[idx]) {row.emplace_back(candidates[idx]);dfs(candidates, target - candidates[idx], idx, row, ans);row.pop_back();}// 跳过当前下标数字dfs(candidates, target, idx + 1, row, ans);}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<vector<int>> ans;vector<int> row;dfs(candidates, target, 0, row, ans);return ans;}
};

c

void dfs(int *candidates, int candidatesSize, int target, int idx, int *row, int rowSize, int **ans, int *returnSize,int **returnColumnSizes) {if (idx == candidatesSize) {// 尝试到底，开始回溯return;}if (target == 0) {// 符合条件的一个组合ans[*returnSize] = (int *) malloc(sizeof(int) * rowSize);memcpy(ans[*returnSize], row, sizeof(int) * rowSize);(*returnColumnSizes)[*returnSize] = rowSize;++(*returnSize);return;}// 选择当前下标数字if (target >= candidates[idx]) {row[rowSize] = candidates[idx];dfs(candidates, candidatesSize, target - candidates[idx], idx, row, rowSize + 1, ans, returnSize,returnColumnSizes);}// 跳过当前下标数字dfs(candidates, candidatesSize, target, idx + 1, row, rowSize, ans, returnSize, returnColumnSizes);
}/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int **combinationSum(int *candidates, int candidatesSize, int target, int *returnSize, int **returnColumnSizes) {*returnSize = 0;*returnColumnSizes = (int *) malloc(sizeof(int) * 150);int **ans = (int **) malloc(sizeof(int *) * 150);int row[target];dfs(candidates, candidatesSize, target, 0, row, 0, ans, returnSize, returnColumnSizes);return ans;
}

python

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:ans = []def dfs(target: int, idx: int, row: List[int]):if idx == len(candidates):# 尝试到底，开始回溯returnif target == 0:# 符合条件的一个组合ans.append(row.copy())return# 选择当前下标数字if target >= candidates[idx]:row.append(candidates[idx])dfs(target - candidates[idx], idx, row)row.pop()# 跳过当前下标数字dfs(target, idx + 1, row)dfs(target, 0, [])return ans

java

class Solution {public List<List<Integer>> combinationSum(int[] candidates, int target) {List<List<Integer>> ans = new ArrayList<>();this.dfs(candidates, target, 0, new LinkedList<>(), ans);return ans;}private void dfs(int[] candidates, int target, int idx, Deque<Integer> row, List<List<Integer>> ans) {if (idx == candidates.length) {// 尝试到底，开始回溯return;}if (target == 0) {// 符合条件的一个组合ans.add(new ArrayList<>(row));return;}if (target >= candidates[idx]) {// 选择当前下标数字row.addLast(candidates[idx]);this.dfs(candidates, target - candidates[idx], idx, row, ans);row.pollLast();}// 跳过当前下标数字this.dfs(candidates, target, idx + 1, row, ans);}
}