Given a list of numbers, find the number of tuples of size N that add to S.

for example in the list (10,5,-1,3,4,-6), the tuple of size 4 (-1,3,4,-6) adds to 0.

题目：

给一数组，求数组中和为S的N个数

思路：

回溯法，数组中每个数都有两种选择，取或者不取；

当选择的数等于N时，则判断该数之和是否等于S。

代码：

#include <iostream>

#include <vector>

using namespace std;

void GetSum(int sum,vector<int> &result,int *num,int n,int curSum,int index,int count){

    if(count==n+1)

        return;

    if(index==4){

        if(curSum==sum){

            for(int i=0;i<4;i++)

                cout<<result[i]<<" ";

            cout<<endl;

        }

        return;

    }

    int x=num[count];

    result.push_back(x);

    GetSum(sum,result,num,n,curSum+x,index+1,count+1);

    result.pop_back();

    GetSum(sum,result,num,n,curSum,index,count+1);

}

int main()

{

    int nums[]={10,-5,-5,0,5,4,6};

    int len=sizeof(nums)/sizeof(nums[0]);

    int curSum=0;

    int index=0;

    int count=0;

    int sum=0;

    vector<int> result;

    GetSum(sum,result,nums,len,curSum,index,count);

    return 0;

}

巴特西

（回溯法）数组中和为S的N个数

题目：

思路：

代码：

最新文章

热门文章