编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m

编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来（背包问题求解） - randyjiawenjie的专栏 - 博客频道 - CSDN.NET
输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来。实际上就是一个背包问题。
求解思路：
1.首先判断，如果n>m，则n中大于m的数不可能参与组合，此时置n = m;
2.将最大数n加入且n == m,则满足条件，输出；
3.将n分两种情况求解，（1）n没有加入，取n = n - 1; m = m;递归下去；（2）n加入，取n = n - 1l, m = m - n,递归下去
private static LinkedList<Integer> list = new LinkedList<Integer>();
/**
 * 求解思路：
 * 1.首先判断，如果n>m,则n中大于m的数不可能参与组合，此时置n=m；
 * 2.将最大的数n加入且n==m，则满足条件，输出；
 * 3.将n分两种情况求解：n没有加入，取n=n-1,m=m,递归；
 * 4.n加入，取n=n-1,m=m-n,递归。
 * 5.结束。
 * @param sum
 * @param n
 */
public static void findSum(int sum, int n)
{
if ( n < 1 || sum < 1)
return;
if (sum > n)
{
list.add(n);
findSum(sum - n, n - 1);// n加入，取n=n-1,m=m-n
list.pop();
findSum(sum, n - 1);    // n没有加入，取n=n-1,m=m
}
else
{
System.out.print(sum);  //  sum < n ,直接输出n就可以满足了
for (int i = 0; i < list.size(); i ++)
System.out.print("  "+ list.get(i));
System.out.println();
}
}
http://www.cnblogs.com/pippo0725/articles/2046366.html
5 int length; 6 void PrintSolutions(int *flag) 7 { 8 for (int i=0; i<length; i++) 9 {10 if (flag[i] == 1)11 {12 cout << i+1 << " ";13 }14 }15 cout << endl;16 }17
18 void BagProblem(int m, int n, int *flag)19 {20 if(n<1 || m<1)21 return;22 if(m < n)23 n = m;24 if (n == m)25 {26 flag[n-1] = 1;27 PrintSolutions(flag);28 flag[n-1] = 0;29 }30 flag[n-1] = 1;31 BagProblem(m-n, n-1, flag);32 flag[n-1] = 0;33
34 BagProblem(m, n-1, flag);35 }
http://blog.csdn.net/wuzhekai1985/article/details/6728657
解法二：用循环，其实就是枚举所有组合。对于n ，组合数应该为2^n。我们可以用一个数字 i 来表示组合。如果i = 5，其二进制形式为101，相应的组合为{1, 3}。也就是说，二进制的每一位都代表一个数字，bit0代表数字1，bit1代表数字2，依次类推。当某位为1，表示选中了该位所表示的数字。
void BagProblem_Solution2(int n, int m)
{
if(n < 1|| m < 1)
return;
if(n > m)
n = m;

int num = 1<<n;               //枚举次数
for(int i = 1; i < num; i++)  //枚举所有情况
{
int sum = 0;
int j, k;
for(j = i, k = 1; j != 0; j>>=1, k++) //针对每种情况求和，判断是否满足条件
{
if(j&1)
sum += k;
}
if(sum == m) //如果满足，打印结果
{
for(j = i, k = 1; j != 0; j>>=1, k++)
{
if(j&1)
cout<<k<<' ';
}
cout<<endl;
}
}
}
Read full article from 编程求解，输入两个整数n和m,从数列1,2,3，……n中随意取几个数，使其和等于m。要求将所有的可能组合列出来（背包问题求解） - randyjiawenjie的专栏 - 博客频道 - CSDN.NET