学步园

先来看一道题：给定整数：a1, a2, a3.....an, 判断是否可以从中选出任意个数，使其和等于K, （数字的个数，取1--N个数都可以），

这道题要求找出这N个数中选1，2，3...N个元素的所有组合，如果任何一个组合满足和为K, 就找到了答案，所以：本质上，这道题就是要求出这个集合的所有的组合，怎么求所有的组合？ 我的理解：对任何元素a 属于A集合， 求

子问题1 ：包含这个元素时的组合，

再加上 子问题 2 ：不包含这个元素的组合 

子问题1， 和子问题2本质上又是和包含这两个子问题的父问题本质上是一样的，所以用递归可以解决：如下某个这是一道典型的可以用深度优先算法

// N为数组中元素的总个数, k为所要求的和

bool  dfs(int i, int sum){
if (N ==i ){

return sum == k ;
}
// 不加上a[i]的情况
if (dfs(n + 1, sum)) return true;
// 加上a[i]的情况
if (dfs(n + 1, sum + arry[i])) return true;

// 无论是否加上arry[i],都不能凑成K, 返回false

return false;

     }

所以， 求出某集合的所有的组合，大体上有相同的方法如下：

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

char* arry[] = {"a", "b", "c", "d", "e"};

void dfsAllPermut3(int n, string& out){
if (n == sizeof(arry)/sizeof(char *)){
if(!out.empty())

cout << out <<endl;

return;

}
// 不加上a[i]的情况
dfsAllPermut3(n + 1,  out);


// 加上a[i]的情况
dfsAllPermut3(n + 1, out + arry[n]);
}


int _tmain(int argc, _TCHAR* argv[])
{
string output;

dfsAllPermut3(0, output);

system("pause");
return 0;
}