我要招人

去企业版

首页 > 试题广场 >

加起来和为目标值的组合(二)

[编程题]加起来和为目标值的组合(二)

热度指数：47248 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一组候选数 c 和一个目标数 t ，找出候选数中起来和等于 t 的所有组合。

c 中的每个数字在一个组合中只能使用一次。

注意：

1. 题目中所有的数字（包括目标数 t ）都是正整数
2. 组合中的数字 ( $a_1, a_2, … , a_k$ ) 要按非递减排序 ( $a_1 \leq a_2 \leq … \leq a_k$ ).
3. 结果中不能包含重复的组合
4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。

数据范围: $1 \le n \le 70$ ， $1 \le target \le 100$ ， $1 \le C_i \le 50$

要求：空间复杂度 $O(n)$ ，时间复杂度 $O(2^n)$

示例1

输入

[100,10,20,70,60,10,50],80

输出

[[10,10,60],[10,20,50],[10,70],[20,60]]

说明

给定的候选数集是[100,10,20,70,60,10,50]，目标数是80

示例2

输入

[2],1

输出

[]

算法知识视频讲解

未来0116

发表于 2021-07-11 21:14:17

精华题解一.题目描述NC46加起来和为目标值的组合题目链接:https://www.nowcoder.com/practice/75e6cd5b85ab41c6a7c43359a74e869a?tpId=188&&tqId=38629&rp=1&ru=/activity/oj 展开全文

牛客786963925号

发表于 2021-07-13 19:38:59

精华题解利用set解法对于此题，可以利用「回溯」的思想求解：先尝试某一选择，若满足题目条件，则加到最终结果中；否则撤销该选择，重新进行下一次选择。具体而言，利用「回溯」算法求解此题的步骤如图所示：对于原数组，从第一个位置（为10）开始选，加入到临时数组arr中，并将目前的求和结果加入到cur 展开全文

蒙牛麦片

发表于 2021-07-16 22:28:44

精华题解 NC46 加起来和为目标值的组合题意分析：在给定的数组中找到一些子集，这些子集的和等于target 题解一（回溯）：枚举出所有子集，判断这些子集里面的元素和是不是等于target，等于就加入到最后结果中。代码实现如下： void backtrace(vector<int>& 展开全文

华科不平凡

发表于 2020-08-16 03:15:20

通过DFS实现回溯，关键在于两点：去重（好好理解一下）剪枝（不剪枝会超时） class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, in 展开全文

GoodLuck·HQ

发表于 2020-10-08 15:13:52

import java.util.*; public class Solution { public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) { Arra 展开全文

堆栈哲学

发表于 2021-07-13 12:24:45

解法一：回溯思路步骤：涉及到搜索所有可能的组合类型时，一般情况下都会想到用回溯法。题目中结果集不能重复，这是一个应该注意的点。开两个数组rseult，path存储结果与可能的路径集。处理递归终止情况：sum+=num[i]>target时，终止循环（sum为组合数和）利用一个n 展开全文

牛一霸

发表于 2021-07-11 22:03:04

题目：加起来和为目标值的组合描述：给出一组候选数 C和一个目标数 T，找出候选数中起来和等于 T的所有组合。 C中的每个数字在一个组合中只能使用一次。注意：题目中所有的数字（包括目标数 T）都是正整数，组合中的数字(a1,a2,…,a 展开全文

leaves0924

发表于 2021-10-14 23:45:02

题目描述给出一组候选数 c和一个目标数 t，找出候选数中和等于t的所有组合。 c中每个数字在一个组合中只能使用一次。注意： 1.题目中所有的数字都是正整数。 2.组合中数字（a1,a2...ak）要按非递减排序。 3.结果中不能包含重复的组合。 4.组合之间的排序按照索引从小到大依次比较，小的排展开全文

牛客402413417号

发表于 2022-03-15 20:16:29

代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 @param num int整型一维数组 @param target int整型 @return int整型二维数组 import json class Solution: # def init(self): # 展开全文

wyg_031113

发表于 2020-10-26 08:47:53

解法1：暴力DFS+剪枝 class Solution { public: vector<vector<int> > ans; vector<int> one; vector<vector<int> > combin 展开全文

勤奋的猫

发表于 2022-06-22 19:47:47

import java.util.* ; public class Solution { public ArrayList<ArrayList<Integer>>&nb 展开全文

摸鱼学大师

发表于 2022-02-05 09:47:16

题目主要信息: 需要从数组num找出所有加起来等于target的组合每个组合num中每个元素只能用1次返回的值必须是非递减次序，组合不能重复具体思路: 对于有序的num数组中第一个元素，我们可以考虑如果它比target大，那么后续元素都会比target大，后面就不会有加起来等于target 展开全文

猪猪向前冲

发表于 2022-03-03 22:57:34

class Solution { public: vector<vector<int> > combinationSum2(vector<int> &num, 展开全文

问题信息

数组回溯

难度：

103条回答 508收藏 21737浏览

通过挑战的用户

牛客24353...

2022-09-15 22:42:26
牛客5183276号

2022-09-15 22:08:29
知有csp

2022-09-15 17:00:58
彭三岁

2022-09-15 16:46:34
牛客21276...

2022-09-14 23:42:42

加起来和为目标值的组合(二)

输入

输出

说明

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题