困惑了一个晚上的有关问题= =求思路

困惑了一个晚上的问题= =求思路
大概就是从一堆数中找出所有组合 满足：组合里的数为的和为一个数
举个栗子
输入：
9 / /和为9
1 2 3 3 9 / / 5个数
输出
1 2 3 4 / /既第1234个数可以是一个组
5 / /既第5个数可以是一个组


拜托拜托 帮忙指点下思路  之前百度过有的说事遍历 但是我觉得我的题目没法遍历- -
------解决思路----------------------
遍历没说错，只是光遍历不行，还要回溯。

对于第一个数，如果是解的一部分，那么，继续处理剩下的几个数，总和调整为9-1=8，剩下的数递归处理
同时再考虑第一个数不是解的一部分，那么对剩下的4个数继续处理，总和还是9，递归之
------解决思路----------------------
先按从大到小排序，然后深搜
------解决思路----------------------
01背包问题，这里给个代码，供参考。

#define N 1000

int input[N+1];

int path[N+1];

void PrintComm( int n, int a[], int curSum, int curIndex, int totalSum );

int main(int argc, char* argv[])

{

	int n,sum,i;

	scanf("%d%d", &n, &sum);//输入数字个数与要求的和

    for ( i=0; i<n; i++ ) scanf( "%d", &input[i+1] );

	input[0] = 0;

	path[0] = 0;

	PrintComm(n, input, 0, 0, sum);

	return 0;

}



void PrintComm( int n, int a[], int curSum, int curIndex, int totalSum )

{


	 int i;

     if ( curIndex > n ) return;

	 if ( curSum == totalSum )  //和相等输出路径

	 {

	     for ( i=0; i<=curIndex; i++ )

		 {

		     if ( path[i] ) printf( "%d ", i );

		 }

		 printf( "\n" );

		 return;

	 }

	 if ( curSum > totalSum ) return;


     path[curIndex+1] = 0;

     PrintComm(n, a,curSum, curIndex+1, totalSum);

     path[curIndex+1] = 1;

     PrintComm(n,a,curSum+a[curIndex+1], curIndex+1, totalSum);

}