寻找和为定值的多个数

题目描述

输入n个数，输出和为sum的组合

题目思路

• DFS+回溯
• 加上一些约束条件，代码中需要加入一些相应的判断
• 限制组合中数的个数为k，考虑去除重复组合

代码

#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define N 100
int a[N];
//和为sum，n是下标，递归+回溯 
void sumOfkNumber(vector<int>& v,int sum,int index,int k){
    if(v.size()==k&&sum==0){
        for(std::vector<int>::iterator m=v.begin();m!=v.end();m++){
            cout<<*m<<" ";
        }
        cout<<endl;
        return;
    }
    if(sum<0||index<0){
        return;
    }
    //去重复 (因为已经是排好序的了)
    while(index>0&&a[index]==a[index-1]){
        index--;
    }
    //a[n]取，则sum-a[n],不取，则sum，n-1是下个数的下标 
    v.push_back(a[index]);
    sumOfkNumber(v,sum-a[index],index-1,k);
    v.pop_back();
    sumOfkNumber(v,sum,index-1,k);
}
int main() {
    //freopen("in.txt","r",stdin);
    int n,sum,k;
    cin>>n>>sum>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n);
    vector<int> v;
    sumOfkNumber(v,sum,n-1,k);
    //fclose(stdin);
    return 0;
}