首页 > 试题广场 >

组合之和

[编程题]组合之和
  • 热度指数:9890 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一组候选数C和一个目标数T,找出候选数中加起来和等于T的所有组合。
C中的数字在组合中可以被无限次使用
注意:
  • 题目中所有的数字(包括目标数T)都是正整数
  • 你给出的组合中的数字 (a 1, a 2, … , a k) 要按非递减排序 (ie, a 1 ≤ a 2 ≤ … ≤ a k).
  • 结解集中不能包含重复的组合
例如:给定的候选数集是[20,30,60,70],目标数是7
解集是:
[70]
[20, 20, 30]
对于没一次选择 有两种可能 用和不用
选择用之后,下一次仍然可以用 所以k不加1
选择不用 就移到下一个数 k加1
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > res;
        vector<int> temp;
        sort(candidates.begin(), candidates.end());
        Sum(res, temp, candidates, 0, target);
        return res;
    }
    void Sum(vector<vector<int>> &res, vector<int> &temp, vector<int> &candidates, int k, int target) {
        if (target == 0)
        {
            res.push_back(temp);
            return;
        }
        if (target < 0||k >= candidates.size())
            return;
        vector<int>t=temp;
        temp.push_back(candidates[k]);
        Sum(res, temp, candidates, k , target- candidates[k]);//用
        Sum(res, t, candidates, k + 1, target);//不用
    }
};

发表于 2018-05-26 22:02:38 回复(1)
因为允许重复把回溯法下次的判断还从他自己开始就可以了,不重复的话就从下一个开始,本质就是DFS
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        ArrayList<Integer> list=new ArrayList<>();
        combination(candidates,target,list,0);
            return res;
    }
    public void combination(int[] candidates,int target,ArrayList<Integer> list,int start){
        if(target==0){res.add(new ArrayList<Integer>(list));
                               return;}
        if(target<0){return;}
        for(int i=start;i<candidates.length;i++){
            list.add(candidates[i]);
            combination(candidates,target-candidates[i],list,i);
            list.remove(list.size()-1);
        }
    }
}

编辑于 2019-03-10 12:13:20 回复(0)
class Solution {
    vector<int> d;
    vector<vector<int> > z;
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,target,0);
        return z;
    }
    void dfs(vector<int> &candidates,int x,int t,int step)
    {
        if(x>t||x<0) return ;
        if(x==t){z.push_back(d);}
        else
        {
            int i;
            for(i=step;i<candidates.size();i++)
            {
                d.push_back(candidates[i]);
                dfs(candidates,x+candidates[i],t,i);
                d.pop_back();
            }
        }
    }
};

发表于 2016-08-17 10:13:00 回复(0)
class Solution {
	vector<int> d;
	vector<vector<int> > result;
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        dfs(candidates,0,target,0);
        return result;
    }
    void dfs(vector<int> &candidates,int sum,int target,int step)
    {
    	if(sum > target || sum < 0)
    		return;
    	if(sum == target)
    		result.push_back(d);
    	else{
    		for(int i=step;i<candidates.size();i++)
    		{
    			d.push_back(candidates[i]);
    			dfs(candidates, sum+candidates[i], target, i);
    			d.pop_back();
			}
		} 
	}
};


发表于 2017-08-29 01:26:40 回复(0)
class Solution {
public:
    vector<vector<int> > res;
    void dfs(set<int> &s, int target,vector<int> v, set<int>::iterator it){
        if(target == 0){
            res.push_back(v);
            return;
        }
        while (it != s.end()){
            if(target - *it >= 0) {
                v.push_back(*it);
                dfs(s, target - *it, v,it);
                v.pop_back();
            }
            it ++;
        }
    }
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        set<int> s(candidates.begin(),candidates.end());
        vector<int> v;
        dfs(s, target,v,s.begin());
        return res;
    }
};

发表于 2019-06-04 21:01:13 回复(0)
最开始AC 的耗时为110ms,最后优化到了7ms。可怕。。。。。
class Solution {
private: vector<vector<int>> res;
public: vector<vector<int>>  combinationSum(vector<int> &candidates, int target) {
        int sum = 0;
        vector<int> path;
        sort(candidates.begin(), candidates.end());
           int index = 0;
        DFS(candidates, path, sum, target,index);
        return res;
    }
    void DFS(vector<int> &arr, vector<int> &path, int &sum, const int &target, int index) {
        if (sum > target)  return;
        if (sum == target) {
            res.push_back(path);
            return;
        }
        for (int i = index; i != arr.size(); i++) {
            sum += arr[i];
            path.push_back(arr[i]);
            DFS(arr, path, sum, target,i);
            sum =sum - arr[i];
            path.pop_back();
        }
    }
};

发表于 2018-01-09 20:20:26 回复(0)
10行Python搞定,用了lambda
class Solution(object):
    def combinationSum(self, c, t, k=0):
        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.combinationSum(c, t - c[i], i)))
        return res
发表于 2017-10-08 13:06:40 回复(0)
class Solution {
public:
void backTracking(vector<int> &candidates,vector<vector<int>> &res,vector<int> &combine,int target,int begin)
{
    if(target==0)
    {
        res.push_back(combine);
        return;
    }
    for(int i=begin;i<candidates.size();i++)
    {
        if(target-candidates[i]<0) return;
        combine.push_back(candidates[i]);
        backTracking(candidates,res,combine,target-candidates[i],i);
        combine.pop_back();
    }
}
/// 使用所给的整数能够组成和为target的组合有多少种,元素可以重复使用无限次
vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
   vector<vector<int>> res;
   vector<int> combine;
   int len=candidates.size();
   if(len==0) return res;
   sort(candidates.begin(),candidates.end());
   backTracking(candidates,res,combine,target,0);
   return res;
}
};

发表于 2017-07-16 09:15:58 回复(0)
回溯法详解
其它套路参考,归纳共性
http://blog.csdn.net/versencoder/article/details/52072350
public class Solution { List<List<Integer>> result=new ArrayList<List<Integer>>(); public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); List<Integer> list=new ArrayList<Integer>(); 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){ result.add(new ArrayList<>(list)); }else{ for(int i=start;i<candidates.length;i++){ list.add(candidates[i]); backtracking(candidates,target-candidates[i],i,list); list.remove(list.size()-1); } } } }

编辑于 2016-07-30 20:09:23 回复(0)

class Solution {
public:
vector<vector<int>>res;
vector<int>path;
void recur(vector<int>candidates,int target,int sum,int start_index)
{
if(sum>=target)
{
if(sum==target)
{
res.push_back(path);;
}
return;
}</int></int></int>

    for(int i=start_index;i<candidates.size();i++)
    {
        path.push_back(candidates[i]);
        recur(candidates, target, sum+candidates[i], i);
        //向下递归的时候,这次用了下次还能用
        path.pop_back();
    }


}
vector<vector<int> > combinationSum(vector<int> &candidates, int target) 
{
    res.clear();path.clear();
    if(candidates.empty()) return res;

    sort(candidates.begin(), candidates.end());
    recur(candidates, target, 0, 0);

    return res;
}

};

发表于 2022-03-24 10:33:09 回复(0)
class Solution {
public:
  vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
    sort(begin(candidates), end(candidates));
    vector<vector<int>> ans;
    vector<int> curr;
    function<void(int, int)> backtracking = [&](int p, int s) {
      if (!s) return ans.push_back(curr);
      for (int i = p; i < candidates.size(); ++i) {
        if (s - candidates[i] < 0) return;
        curr.emplace_back(candidates[i]);
        backtracking(i, s - candidates[i]);
        curr.pop_back();
      }
    };
    backtracking(0, target);
    return ans;
  }
};

发表于 2021-09-22 13:03:43 回复(0)
import java.util.*;

public class Solution {
    private LinkedHashSet<ArrayList<Integer>> resSet = new LinkedHashSet<ArrayList<Integer>>();
    private int[] num;
    private ArrayList<Integer> res = new ArrayList<Integer>();
    
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<ArrayList<Integer>>();
        
        if (candidates == null || candidates.length == 0 || target <= 0)
            return resList;
        
        Arrays.sort(candidates);
        this.num = candidates;
        getCombinationSum(0, target);
        
        resList.addAll(resSet);
        return resList;
    }
    
    private void getCombinationSum(int index, int target) {
        if (target < 0)
            return ;
        
        if (target == 0) {
            resSet.add((ArrayList<Integer>)res.clone());
            return ;
        }
        
        if (index == num.length)
            return ;
        
        if (num[index] > target)
            return ;
        
        res.add(num[index]);
        getCombinationSum(index, target - num[index]);
        res.remove((Integer)num[index]);
        
        getCombinationSum(index + 1, target);
    }
}
发表于 2020-08-31 17:44:14 回复(0)
import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
		Arrays.sort(candidates);
		dfs(candidates,target,0,new ArrayDeque<>(),res);
		return res;
    }
    private void dfs(int[] candidates, int residue, int begin, Deque<Integer> path, ArrayList<ArrayList<Integer>> res) {
		if (residue == 0) {
			res.add(new ArrayList<>(path));
		}
		for (int i = begin; i < candidates.length; i++) {
			if (residue - candidates[i] < 0) {
				break;
			}
			path.addLast(candidates[i]);
			dfs(candidates, residue - candidates[i], i, path, res);
			path.removeLast();
		}
	}
}

发表于 2020-08-01 16:30:04 回复(0)
class Solution {
public:
    void dfs(vector<int> &num,vector<vector<int> > &vv,vector<int> &v,int k,int target){
        if(target==0){
            vv.push_back(v);
            return;
        }
        if(k>=num.size() || target < num[k])
            return;
        v.push_back(num[k]);
        dfs(num,vv,v,k,target-num[k]); //用原来这个数
        v.pop_back();
        dfs(num,vv,v,k+1,target);  // 跳过原来的数用下一个数
    }
    
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        vector<vector<int> > vv;
        if(candidates.size()==0)
            return vv;
        sort(candidates.begin(),candidates.end());
        vector<int> num;
        num.push_back(candidates[0]);
        for(int i=1;i<candidates.size();i++){
            if(candidates[i]!=num.back())
                num.push_back(candidates[i]);
        }
        vector<int> v;
        dfs(num,vv,v,0,target);
        return vv;
    }
};

发表于 2020-04-29 15:41:02 回复(0)
class Solution {
private:
    vector<vector<int>>  res;
    vector<int> temp;
    int sum;
public:
    
    void DFS(vector<int> temp, int target, int sum, vector<int> &candidates, int stat)
{
	if (sum == target)
	{
		res.push_back(temp);
		return;
	}
	for (int i = stat; i<candidates.size(); i++)
	{
		sum += candidates[i];
		temp.push_back(candidates[i]);
		if (sum  <= target)
		{
			
			DFS(temp, target, sum , candidates, i);
			
		}
		temp.pop_back();
		sum -= candidates[i];
	}
}

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) 
    {
        sort(candidates.begin(),candidates.end());
        DFS(temp, target, 0, candidates, 0);
        return res;
    }
};

发表于 2020-04-07 12:29:18 回复(0)
class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> res;
        vector<int> temp;
        dfs(res, temp, 0, candidates, target);
        return res;
    }
    
    void dfs(vector<vector<int>> &res, vector<int> &temp, int k, vector<int> &candidates, int left) {
        if (left == 0) {
            res.push_back(temp);
            return;
        }
        for (int i = k;i < candidates.size();i++) {
            if (i > k && candidates[i] == candidates[i - 1]) {
                continue;
            }
            if (candidates[i] <= left) {
                temp.push_back(candidates[i]);
                dfs(res, temp, i, candidates, left - candidates[i]);
                temp.pop_back();
            }
        }
    }
};

发表于 2020-01-10 23:09:28 回复(0)
import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return ret;
        }
        Arrays.sort(candidates);
        ArrayList<Integer> tempList = new ArrayList<>();
        backtracking(candidates, ret, tempList, 0, target);
        return ret;
    }
    
    private void backtracking(int[] candidates,ArrayList<ArrayList<Integer>> ret, ArrayList<Integer> tempList, int start, int target) {
        if (target == 0) {
            ret.add(new ArrayList<>(tempList));
        }
        
        for(int i = start; i < candidates.length; ++i) {
            if (candidates[i] <= target) {
                tempList.add(candidates[i]);
                backtracking(candidates, ret, tempList, i, target - candidates[i]);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

发表于 2019-12-16 22:28:38 回复(1)
import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
    public ArrayList<ArrayList<Integer>> combinationSum(int[] num, int target) {
        if(num == null || num.length == 0 || target <= 0)
            return res;
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        Solve(num, list,0, target, 0);
        return res;
    }
    public void Solve(int[] num, ArrayList<Integer> list, int start, int target, int sum){
        if(sum == target){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        if(sum > target){
            return;
        }
        for(int i = start; i < num.length; i++){
            if(sum < target){
                list.add(num[i]);
                sum += num[i];
                Solve(num, list,i,target, sum);
                list.remove(list.size() - 1);
                sum -= num[i];
            }
        }
        return;
    }
}

发表于 2019-09-07 18:20:52 回复(0)
真的是服了牛客网抄过来的题,题是抄过来了,麻烦测试数据注意一下行么!题解说数组非降序,给的测试用例又是没有排序的!!!!
发表于 2019-07-17 14:44:16 回复(1)
import java.util.*;

public class Solution {

    /**
     * 在C中找[所有加起来等于T]的集合
     * 1.C中的元素可以重复使用
     * 2.所有数为正
     * 3.非递减排序
     * 
     * 思路:分解问题。对于C中的某一个元素来说,当使用了这个元素时,
     * combinationSum(candidates,target,idx) -> combinationSum(candidates,target-candidates[i],i)
     * 
     * 测试用例设计:
     * 7 4 2 1    11
     * 2 4 3 8    1
     * 3 7 11 13  11
     */
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        //题目没有有序,所以排序
        Arrays.sort(candidates);
        ArrayList<ArrayList<Integer>> res = combinationSumCore(candidates, target, 0);
        return res != null ? res : new ArrayList<>();
    }

    private ArrayList<ArrayList<Integer>> combinationSumCore(int[] candidates, int target, int idx) {
        if (idx >= candidates.length) return null;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int i = idx; i < candidates.length; i++) {
            //当前target小于当前元素
            if (target < candidates[i]) break;
            //当前target等于当前元素
            else if (candidates[i] == target) {
                ArrayList<Integer> t = new ArrayList<>();
                t.add(candidates[i]);
                res.add(t);
            } else {
                //当前target大于当前元素
                ArrayList<ArrayList<Integer>> temp = combinationSumCore(candidates, target - candidates[i], i);
                if (temp != null) {
                    for (int j = 0; j < temp.size(); j++) {
                        ArrayList<Integer> t = temp.get(j);
                        t.add(0, candidates[i]);
                        res.add(t);
                    }
                }
            }
        }
        return res.size() != 0 ? res : null;
    }
}
编辑于 2019-05-24 13:06:41 回复(0)