这个程序是从小到大输出所给的几个数的所有组合。编01背包问题时我遇到了个困难，就是一个包只能用一次，但是如何排除重复的情况呢？比如求2,3,7的组合，有2,3,4,5,6,7,8....错了吧，4,6,8哪来的？因为我没有考虑到4=2+2，6=3+3，8=4+4的重复的现象，如果不增加一个很麻烦的步骤判断之前是否曾经出现过当前要加的数，实在想不到有什么简洁的方法了，这就是check()这堆垃圾诞生的原因。不知道有没有简单的方法啊？

#include <iostream>

using namespace std;

int comnum[100];

int check (int hash[], int i, int j)
{
    int x = j, f = i - j, ci = 0;

    if (hash[f] == 0)
        return 0;
    comnum[ci++] = x;

    int f0 = f;
    // search x
    while (hash[f] != -1) {
        int a = hash[f];
        int b = f - a;
        if (x == b)
            return 0;
        comnum[ci++] = b;
        f = a;
    }
    if (x == f)
        return 0;
    comnum[ci++] = f;
    // show
    cout << i << '=';
    for (int k = 0; k < ci - 1; ++k)
        cout << comnum[k] << '+';
    cout << comnum[ci - 1] << '\n';

    return f0;
}

int knap (int org[], int n, int hash[])
{
    int sum = 0;

    for (int i = 0; i < n; ++i)
        hash[org[i]] = -1;
    for (int i = 0; i < n; ++i)
        sum += org[i];
    for (int i = 0; i <= sum; ++i)
        if (hash[i] == 0)
            for (int j = 0; org[j] < i && j < n; ++j) {
                int f = check (hash, i, org[j]);
                if (f) {
                    hash[i] = f;
                    break;
                }
            }

    return sum;
}

int main ()
{
    int org[5] = {3,5,7,11,13};
    int hash[100] = {0};

    int sum = knap (org, 5, hash);

system ("pause");
    return 0;
}