首页 > 试题广场 >

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

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

热度指数：47243 时间限制：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

输出

[]

算法知识视频讲解

查看答案及解析

Java

又笨又懒不想上课

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();
    ArrayList<Integer> ls = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        int[] used = new int[num.length];
        Arrays.sort(num);
        dfs(num,target,used,0);      
        return res;
    }
    private void dfs(int[] a, int target,int[] used,int start){
        if(target == 0 && !res.contains(ls)) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for(int i = start; i < a.length && target > 0; i++) {           
            if(used[i] == 1) continue;
            used[i] = 1;
            ls.add(a[i]);
            target -= a[i];
            dfs(a,target,used,i);
            ls.remove(ls.size()-1);
            target += a[i];
            used[i] = 0;
        }
    }
}

发表于 2021-06-16 10:02:35 回复(1)

C/C++

方块儿脑袋

DFS,只需要前期对candidates的排序,后期不需要对返回结果排序.只需要在同一层DFS的时候检查相邻元素是否相同,避免从相同元素在同一层开始DFS就可以

vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        // DFS
        // 先对candidates排序
        sort(candidates.begin(), candidates.end());
        
        vector<vector<int> > res;
        if (candidates.empty()) return res;
        vector<int> tmp;
        
        DFS(candidates, res, tmp, target, 0);
        
        return res;
    }
    
    void DFS(vector<int> candidates, vector<vector<int> > &res, vector<int> tmp, int target, int start) {
        if (target == 0) {
            res.push_back(tmp);
            return ;
        }
        int n = candidates.size();
        if (start >= n) return ;
        
        for (int i = start; i < n; i ++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue; // 去重
            
            if (candidates[i] <= target) {
                tmp.push_back(candidates[i]);
                DFS(candidates, res, tmp, target - candidates[i], i + 1);
                tmp.pop_back();
            }
        }
        
    }

发表于 2019-06-18 14:37:44 回复(1)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  vector<vector<int>> combinationSum2(vector<int> &nums, int target) {
    const int n = nums.size();
    sort(begin(nums), end(nums));
    
    vector<vector<int>> ans;
    vector<int> candidates;
    function<void(int, int)> backtracking_algorithm = [&](int p, int sum) -> void {
      if (sum == 0)
        return ans.push_back(candidates);
      
      for (int i = p; i < n; ++i) {
        if (i > p && nums[i] == nums[i - 1]) continue; // deduplication 去重
        if (sum - nums[i] < 0) return; // pruning 强剪技
        candidates.emplace_back(nums[i]);
        backtracking_algorithm(i + 1, sum - nums[i]);
        candidates.pop_back();
      }
    };

    backtracking_algorithm(0, target);
    return ans;
  }
};

发表于 2021-07-19 10:36:32 回复(1)

别看我只是一只羊

    本题解法详细见  

    http://blog.csdn.net/versencoder/article/details/52071930  

    查看其它类型题目  

    http://blog.csdn.net/versencoder/article/details/52072350

public class Solution {

List<List<Integer>> result=new ArrayList<List<Integer>>();

//List<Integer> temp=new ArrayList<Integer>();

public List<List<Integer>> combinationSum2(int[] candidates, int target) {

List<Integer> list=new ArrayList<Integer>();

Arrays.sort(candidates);

backtracking(candidates,target,0,list);

return result;

}

public void backtracking(int[] candidates,int target,int start,List<Integer> list){

if(target<0) return ;

else if(target==0){

//temp=new ArrayList<Integer>(list);

//if(!result.contains(temp))

//result.add(temp);

result.add(new ArrayList(list));

}

else{

for(int i=start;i<candidates.length;i++){

if(i>start&&candidates[i]==candidates[i-1]) continue;

list.add(candidates[i]);

backtracking(candidates,target-candidates[i],i+1,list);

list.remove(list.size()-1);

}

发表于 2016-07-30 20:10:45 回复(1)

Java

quwhsk

import java.util.*;

public class Solution {
    private ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        //    首先进行排序，这样能够保证输出按照非递减顺序排列 -> 【10，10，60】...
        Arrays.sort(num);
        helper(num, 0, target, new ArrayList<Integer>());
        return ans; 
    }
    
    //    搜索可行解
    private void helper(int[] num, int index, int target, ArrayList<Integer> tmp){
        //    这里采用了target - num[index]的形式求解
        //    每一轮搜索，target值都会减小，如果小于0，返回
        if(target < 0)
            return ;
        //    如果等于0，说明找到了一组可行解，将其添加到解集ans中
        if(target == 0)
            ans.add(new ArrayList<Integer>(tmp));
        
        //    从这里开始一次尝试
        for(int i = index; i < num.length; i ++){
            //    如果叠加的数值之和 + 当前值 > target，
            //    由于这组数据是排序完成的，所以不必尝试后续的数值
            //    比如：【10，10，20，50】，叠加数值之和已经超过target【80】，
            //    后续的【10，10，20，60】、【10，10，20，70】不必再尝试，即便出现重复也是如此
            if(target - num[i] < 0)
                break;
            //    希望跳过重复的解集，比如出现重复的数值【10，10，60，60，60，70】，target还是80
            //    那么，【10，10，60】只需要一组就可以了
            if(i > index && num[i] == num[i - 1])
                continue ;
            
            //    上述是排除一些明显可以不必尝试的情况，除去这部分内容，可以继续尝试搜索后续的可行解
            //    首先添加该数值到临时解集tmp中
            tmp.add(num[i]);
            //    然后尝试向后搜索
            helper(num, i + 1, target - num[i], tmp);
            //    回溯时，需要删除tmp中的最后数值【这儿可能添加了一个数值，使得整体的叠加值 > target等】
            tmp.remove(tmp.size() - 1);
        }
    }
}

发表于 2021-11-14 09:40:29 回复(0)

Java

妮可芝麻尻

java原题模版没给import java.util.*;

发表于 2021-10-24 18:29:09 回复(0)

Java

summmmmer1997

import java.util.*;
public class Solution {
    ArrayList> res;
    ArrayList list;
    int target;
    int[] nums;
    public ArrayList> combinationSum2(int[] nums, int target) {
        this.res = new ArrayList();
        this.list = new ArrayList();
        this.nums = nums;
        this.target = target;
        Arrays.sort(nums);
        dfs(0,0);
        return res;
    }

    //从当前index处开始dfs，前面的累计和为sum
    public void dfs(int index,int sum){
        //剪枝，sum超过target后，不可能再匹配到target（升序）
        if(sum > target) 
            return;
        //命中target
        if(sum == target){
            res.add(new ArrayList(list));
            return;
        }
        //下一个元素的选择范围：从index到最后一个元素
       for(int i = index;i < nums.length;i++){
           //去重（重点），参考三数之和
           if(i>index && nums[i] == nums[i-1]) continue;
           //选择当前元素
           list.add(nums[i]);
           dfs(i + 1,sum + nums[i]);
           list.remove(list.size()-1);
       } 
    }

卡时间了，之前的很多提交不能通过了，关键点在于去重操作:
if(i>index && nums[i] == nums[i-1]) continue;

发表于 2021-10-23 15:28:22 回复(0)

蔡徐坤001

首先需要对数组进行排序，这样如果有相同的元素必定会连续的在一起，那么在进行回溯的时候进行数组元素的去重即可

import java.util.*;
public class Solution {
    ArrayList<ArrayList<Integer>> list;
    ArrayList<Integer> path;
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        list = new ArrayList<>();
        path = new ArrayList<>();
        Arrays.sort(num);
        dfs(num,target,0);
        return list;
    }
    public void dfs(int[] num,int target,int index) {
        int sum = 0;
        for(Integer val : path) {
            sum += val;
        }
        if(sum > target) {
            return;
        }else if(sum == target) {
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i = index; i < num.length; i++) {
            if(i > index && num[i] == num[i-1]) continue;
            path.add(num[i]);
            dfs(num,target,i+1);
            path.remove(path.size() - 1);
        }
    }
}

发表于 2021-06-11 23:35:41 回复(0)

Java

惠灵顿靖

回溯+剪枝

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> tmp=new ArrayList<>();
        if(num.length==0||num==null)return res;
        Arrays.sort(num);
        dfs(num,target,tmp,0,res);
        return res;
}
    void dfs(int[] num, int target, ArrayList<Integer> tmp, int start, ArrayList<ArrayList<Integer>> res){
        if(target==0&&!res.contains(tmp)){
            res.add(new ArrayList<Integer>(tmp));//这里注意，一定要new.哭啊哭，我最初在这里卡了好久，如果不new，下次remove(tmp)时候，会把res顺带一起remove掉
            return;
        }
        for(int i=start;i<num.length;++i){
            if(i>start&&num[i]==num[i-1])continue;//去重，这一部分没有也可以
            if(num[i]<=target){//剪枝
                tmp.add(num[i]);
                dfs(num,target-num[i],tmp,i+1,res);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}

发表于 2021-04-16 20:12:35 回复(1)

在开会的芒果很高大

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<Integer> track = new ArrayList<>();
        int sum = 0;
        boolean[] flag = new boolean[num.length];
        Arrays.sort(num);
        backTrack(num,track,target,sum,flag,0);
        return result;
    }
    
    public void backTrack(int[] num,ArrayList<Integer> track,int target,int sum,boolean[] flag,int start){
        //满足结束的条件
        if(sum == target){
            if(result.contains(track)){
                return ;
            }else{
                result.add(new ArrayList<>(track));
                return ;
            }
        }else if(sum > target){    //剪枝
            return ;
        }
        if(track.size() == num.length){    //所有的元素总和还是比 target 小的时候
            return ;
        }
        
        //这里利用一个boolean[] 和 开始位置start 来给出选择列表
        for(int i = start; i < num.length; i++){
            if(num[i] > target){    //剪枝
                return ;
            }
            if(!flag[i]){
                track.add(num[i]);
                sum += num[i];
                flag[i] = true;
                backTrack(num,track,target,sum,flag,i);
                sum -= track.get(track.size()-1);
                flag[i] = false;
                track.remove(track.size()-1);
            }
        }
    }
}

编辑于 2021-03-07 13:45:06 回复(0)

zbbsyx

class Solution {
public:
    vector<vector<int> > res;
    set<string> used;
    void dfs(vector<int> &s, int target,vector<int> v, vector<int>::iterator it,string str){
        if(target == 0){
            if(used.count(str) <= 0){
                res.push_back(v);
                used.insert(str);
            }
            return;
        }
        while (it != s.end()){
            if(target - *it >= 0) {
                v.push_back(*it);
                int num = *it;
                dfs(s, target - num, v, ++it, str + to_string(num) + '#');
                v.pop_back();
            } else{
                return;
            }
        }
    }
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        vector<int> v;
        dfs(candidates, target,v,candidates.begin(),"");
        return res;
    }
};

发表于 2019-06-04 21:27:58 回复(0)

微软内推小王子

最后就是一顿去重

import itertools

class Solution(object):
    def combine(self, c, t, k):
        if t == 0:
            return [[]]
        elif t < 0:
            return []
        res = []
        for i in range(k, len(c)):
            res.extend(map(lambda x: [c[i]] + x, self.combine(c, t - c[i], i + 1)))
        return res

    def combinationSum2(self, c, t):
        res = self.combine(c, t, 0)
        for i in range(len(res)):
            res[i].sort()
        res.sort()
        return list(res for res,_ in itertools.groupby(res))

发表于 2017-10-08 13:29:15 回复(0)

C/C++

nbgao

class Solution {
	vector<int> d;
	vector<vector<int> > result;
	set<vector<int> > s;
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        dfs(num,0,target,0);
        set<vector<int> >::iterator it;
        for(it=s.begin();it!=s.end();it++)
        	result.push_back(*it);
        return result;
    }
    void dfs(vector<int> &num,int sum,int target,int step)
    {
    	if(sum > target || sum < 0)
    		return;
    	if(sum == target)
    		s.insert(d);
    	else{
    		for(int i=step;i<num.size();i++)
    		{
    			d.push_back(num[i]);
    			dfs(num, sum+num[i], target, i+1);
    			d.pop_back();
			}
		} 
	}
};

发表于 2017-08-30 00:57:40 回复(1)

元气の悟空

class Solution {
    vector<int> d;
    vector<vector<int> > z;
    set<vector<int> > s;
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(),num.end());
        dfs(num,0,target,0);
        set<vector<int> >::iterator it;
        for(it=s.begin();it!=s.end();z.push_back(*it),it++);
        return z;
    }
    void dfs(vector<int> &candidates,int x,int t,int step)
    {
        if(x>t||x<0) return ;
        if(x==t){s.insert(d);}
        else
        {
            int i;
            for(i=step;i<candidates.size();i++)
            {
                d.push_back(candidates[i]);
                dfs(candidates,x+candidates[i],t,i+1);
                d.pop_back();
            }
        }
    }
};

发表于 2016-08-17 10:19:12 回复(2)

Java

包子豆腐干

为什么现在答案都运行超时了,这让我这个渣渣怎么做

发表于 2021-08-09 20:44:35 回复(2)

好吧我就是二蛋

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		ArrayList<Integer> list = new ArrayList<Integer>();
		boolean[] visited = new boolean[num.length];
		if(num == null || num.length <= 0) return null;
		Arrays.sort(num);
		dfs(num,visited,target,0,list,result);
		return result;
    }
	public void dfs(int[] num,boolean[] visited, int diff, int start, ArrayList<Integer> list, ArrayList<ArrayList<Integer>> result){
		if(diff == 0 && !result.contains(list)){//找到一个合法解
			result.add(new ArrayList<>(list));//这里要注意！！！！！一定要new
			return;
		}
		for (int i = start; i < num.length; i++) {//扩展状态
			if(diff < num[i]) return ;	//剪枝
			if(!visited[i]){
				list.add(num[i]);			//执行扩展动作
				visited[i] = true;
				dfs(num,visited,diff-num[i],i,list,result);
				list.remove(list.size()-1);			//撤销扩展动作
				visited[i] = false;
			}
		}
    }
}

发表于 2017-09-04 16:37:44 回复(1)

Java

chg_miz

题解都不符合 4. 组合之间的排序按照索引从小到大依次比较，小的排在前面，如果索引相同的情况下数值相同，则比较下一个索引。比如这个情况，[80,10,20,70,60,10,50]，80，第一个组合应该是[80]吧，但是题解第一个组合都是[10,10,60]

发表于 2021-08-09 13:39:02 回复(2)

C++

矜持的微笑

#include <vector>
class Solution {
    private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& num,int target,int sum,int startIndex){
        if(sum==target){
            result.push_back(path);
            return;
        }
        for(int i=startIndex;i<num.size()&&sum+num[i]<=target;i++){
            if(i>startIndex&&num[i]==num[i-1]){
                continue;
            }
            sum+=num[i];
            path.push_back(num[i]);
            backtracking(num,target,sum,i+1);
            sum-=num[i];
            path.pop_back();
        }
    }
public:
   vector<vector<int>> combinationSum2(vector<int>& num, int target) {
        // write code here
        path.clear();
        result.clear();
        sort(num.begin(),num.end());
        backtracking(num,target,0,0);
        return result;
    }
};

编辑于 2024-01-28 17:45:47 回复(0)

给我一个面试吧

import java.util.*;

public class Solution {
    static ArrayList<Integer> list = new ArrayList<>();
    static ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
    static int sum = 0;

    public ArrayList<ArrayList<Integer>> combinationSum2 (int[] num, int target) {
        // write code here
        int length = num.length;
        Arrays.sort(num);
        boolean[] used = new boolean[length];
        dfs(num, length, used, target, sum, 0);
        return ret;
    }

    public void dfs(int[] num, int length, boolean[] used, int target, int sum,
                    int index) {
        if(sum > target){
            return;
        }
        if (target == sum) {
            ret.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < length; i++) {
            
            if(used[i] || i > 0 &&  num[i] == num[i - 1] && !used[i - 1]){
                continue;
            }
            
            if (sum < target) {
                sum += num[i];
                list.add(num[i]);
                used[i] = true;

                dfs(num, length, used, target, sum, i + 1);

                sum -= num[i];
                used[i] = false;
                list.remove(list.size() - 1);
            }
        }
    }
}

发表于 2023-09-01 21:33:13 回复(0)

Java

牛客839384289号

ArrayList<ArrayList<Integer>> res=new ArrayList<ArrayList<Integer>>();

public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
    Arrays.sort(num);
    recur(num ,new boolean[num.length] ,target ,0 ,new ArrayList<>());
    return res;
}

public void recur(int[] num ,boolean[] flag ,int target ,int index ,ArrayList<Integer> list){

    if(target<0){
        return;
    }
    if(target==0){
        res.add(new ArrayList<>(list));
        return;
    }
    for(int i=index;i<num.length;i++){
        //!flag[i-1] 是为了保证重复数字第一次出现时可以被加进去
        if(flag[i] || (i>0 && num[i]==num[i-1] && !flag[i-1])){
            continue;
        }
        flag[i]=true;
        list.add(num[i]);
        recur(num ,flag ,target-num[i] ,i+1 ,list);
        list.remove(list.size()-1);
        flag[i]=false;
    }
}

发表于 2023-05-28 16:30:28 回复(0)