求和为定值的数组的子集,该怎么解决

求和为定值的数组的子集
一个数组 {2,3,7,4,8}
求和为7的子集，一共两个{3,4},{7}
这个怎么弄？
[解决办法]
子集和问题。
[解决办法]
用回溯法做。
[解决办法]
我给写了个。

#include <iostream>
#include <string>
#include <stack>
#include <vector>
using namespace std;

/*
使用回溯法解子集和问题
*/
const int N=5;
int arr[]={2,3,4,7,8};
int sum=7;
int total=0;
vector<int> solution;
bool hasResult = false;

void dfs( int index )
{
if( index==N ){                        //递归到最后一层的下一层，结束
if( total==sum ){                  //判断是否满足条件，满足则输出结果
hasResult = true;
for(int i=0; i<(int)solution.size();i++)
cout<<solution[i]<<" ";
cout <<endl;
}
return;
}

if( total + arr[index] <= sum ){          //加入第index个数是否小于总和，是则加入
total += arr[index];
solution.push_back(arr[index]);
dfs(index+1);
solution.pop_back();                 //回溯，还原状态
total -= arr[index];
}

dfs(index+1);                       //递归搜索未加入第index个数字的情况
}

int main()
{
dfs(0);
if( !hasResult )
cout << "NO SOLUTION!" <<endl;
return 0;
}

[解决办法]
void dfs( int index )
{
    if( index==N ){                        //递归到最后一层的下一层，结束
        if( total==sum ){                  //判断是否满足条件，满足则输出结果
            hasResult = true;
            for(int i=0; i<(int)solution.size();i++)
                cout<<solution[i]<<" ";
            cout <<endl;
        }
        return;
    }

    if( total + arr[index] <= sum ){          //加入第index个数是否小于总和，是则加入
        total += arr[index];
        solution.push_back(arr[index]);
        dfs(index+1);
        solution.pop_back();                 //回溯，还原状态

        total -= arr[index];
    }

    dfs(index+1);                       //递归搜索未加入第index个数字的情况
}

查看更多 下一篇