广西建设职业学院官网网站,最新的网络营销的案例,手机app定制开发,郑州百姓网招聘文章目录39. 组合总和#xff1a;样例 1#xff1a;样例 2#xff1a;样例 3#xff1a;提示#xff1a;分析#xff1a;题解#xff1a;rustgoccpythonjava39. 组合总和#xff1a;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找… 文章目录39. 组合总和样例 1样例 2样例 3提示分析题解rustgoccpythonjava39. 组合总和
给你一个 无重复元素 的整数数组 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 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40 分析
面对这道算法题目二当家的陷入了沉思。遍历或者递归递归比较直观深度优先回溯。题目要求所有可能的组合不能重复本来是需要想办法去重的但是题目规定参数中所有元素互不相同那我们只要选择不同下标的组合就相当于选择了不同元素的组合。 题解
rust
impl Solution {pub fn combination_sum(candidates: Veci32, target: i32) - VecVeci32 {fn dfs(candidates: Veci32, target: i32, idx: usize, row: mut Veci32, ans: mut VecVeci32) {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, idx1, row)}dfs(target, 0, []int{})return ans
}c
class Solution {
private:void dfs(vectorint candidates, int target, int idx, vectorint row, vectorvectorint 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:vectorvectorint combinationSum(vectorint candidates, int target) {vectorvectorint ans;vectorint 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 ListListInteger combinationSum(int[] candidates, int target) {ListListInteger ans new ArrayList();this.dfs(candidates, target, 0, new LinkedList(), ans);return ans;}private void dfs(int[] candidates, int target, int idx, DequeInteger row, ListListInteger 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);}
}非常感谢你阅读本文~ 欢迎【点赞】【收藏】【评论】~ 放弃不难但坚持一定很酷~ 希望我们大家都能每天进步一点点~ 本文由 二当家的白帽子https://le-yi.blog.csdn.net/ 博客原创~
