不同的组合有几种

/*
 * 注意：题目中说明有问题，应该是第2,3,7,14个数的组合和 第2,3,8,14个数的组合
 *       看起来是一样的，都是{3,4,5,17}，那么只视为一种。
 * 但是：第1,4,6,10,11个数的组合{1,2,7,10,9}和第1,4,11,12,13个数的组合
 *       {1,2,9,10,7}并不是同一种，如果对输入的序列进行了排序，那么这两个组合会
 *       变成同一个组合{1,2,7,9,10}，所以不能对输入的序列先排序后处理。  */

/* 本算法不适用于包含负数的情况 */

/*
 * 另1：如果得到答案是96，说明对原始序列进行了排序 
 * 另2：如果得到答案是52，说明不但对原始序列进行了排序，还进行了去重操作。这
 *      是错误的，因为组合可能包含多个相同的数字，去重后把这部分组合丢掉了。
 * 另3：如果得到答案是223，说明没有排除组合完全一致的情况（例如第2,3,7,14个数的组合和 
 *      第2,3,8,14个数的组合）
 * 另4：如果得到答案是2，说明你求的是满足条件的子序列（下标连续，如{4,2,6,7,5,5}
 *      或{10,9,10}）的个数
 * 另5：如果得到答案是152，说明求的是满足条件：“构成组合的数字不能重复”的组合个数
 */
#include "stdafx.h"
#include<iostream>
#include<vector>
#include<set>
using namespace std;

void SubSet(vector<int>& arr, set<vector<int>>& set, vector<int>& tmp, int index, int sum)
{
    //越界返回
    if (index == arr.size()) return;
    //边界条件不满足返回
    if (sum < 0) return;
    //找到满足条件的子集
    if (arr[index] == sum)
    {
        //纪录子集的最后一个元素
        tmp.push_back(arr[index]);
        //将子集的副本保存
        set.insert(tmp);
        //删除最后一个加入的元素
        tmp.pop_back();

        //如果不选取index对应的数字时，求能得到的满足条件的子集
        SubSet(arr, set, tmp, index + 1, sum);
        return;
    }
    /******** arr[index] <> sum的情况 *********/
    tmp.push_back(arr[index]);
    //选取当前元素的方案：
    SubSet(arr, set, tmp, index + 1, sum - arr[index]);
    tmp.pop_back();
    //不选取当前元素的方案：
    SubSet(arr, set, tmp, index + 1, sum);
}


int _tmain(int argc, _TCHAR* argv[])
{
    int Num/*序列大小*/, SUM/*子集和*/;
    cin >> Num >> SUM;
    //序列
    vector<int> Arr(Num, 0);
    for (unsigned i = 0; i < Num; i++)
    {
        cin >> Arr[i];
    }
    //临时存放子集
    vector<int> Tmp;
    //存放所有子集
    set<vector<int>> sets;
    //求解所有子集
    SubSet(Arr, sets, Tmp, 0, SUM);
    //子集个数---136
    cout << sets.size() << endl;
    //子集详情
    for (auto a : sets)
    {
        for (auto b : a)
            cout << b << " ";
        cout << endl;
    }
    return 0;
}

简单粗暴解法：就是从11个数里面选3个，有11*10*9/6=156，再看答案就可以了

import java.util.*;

public class HelloWorld{
        static int num=0;
      static  int a[]={1, 3, 4, 2, 6,7,5,5,8,10,9,10,7,17};
    static  ArrayList list=new ArrayList();
        static  TreeSet set=new TreeSet();
     public static void main(String []args){
      
     
          digui(0,29);
          
      
      System.out.println(set.size());
          
          
          Iterator<String> it = set.iterator();
while (it.hasNext()) {
  String str = it.next();
  System.out.println(str);
}
     }
     public static void digui(int ge,int sum){
                if(ge>=a.length||sum<=0){
                    if(sum==0){
                    
                      set.add(list.toString());
                    }
                    return;
                }
                list.add(a[ge]);
                digui(ge+1,sum-a[ge]);
                list.remove((Integer)a[ge]);
                digui(ge+1,sum);
         
         
         
         
         
     }
}
为什么答案是143？

import java.util.*;

	



	public class Test {



	



	 public static int sum(ArrayList<Integer> tmp)



	 {



	 int sum = 0;



	 for(int i : tmp)



	 sum += i;



	 return sum;



	 }



	    public static void dfs(int[] S, int index, ArrayList<Integer> tmp, Set<ArrayList<Integer>> ret) {



	     if( sum(tmp) == 29)



	     ret.add(new ArrayList<Integer>(tmp));// 1  需要复制出来一个对象



	        for (int i = index; i < S.length; i++) {



	            tmp.add(S[i]);



	            dfs(S, i + 1,tmp, ret);



	            tmp.remove(tmp.size() - 1);



	        }



	    }



	



	 public static void main(String[] args) {



	



	 int a[] = {1, 3, 4, 2, 6,7,5,5,8,10,9,10,7,17};



	 Set<ArrayList<Integer>> result = new HashSet<ArrayList<Integer>> ();



	 dfs(a, 0,new ArrayList<Integer>(), result);



	 System.out.println(result.size());



	 



	 }



	


}

答案错了，应该是96吧，之前写了这个算法，跑出来是96个组合

import copy
import operator


def answer1(a, answer_num, all_nums, all_num_list):

    if len(a) == 1:
        return 0
    branch_sum_num = 0
    for i in range(len(a)):
        all_nums.append(a[i])
        next_answer_num = answer_num - a[i]
        if next_answer_num == 0:
            all_num_list.append(all_nums)
            branch_sum_num += 1
        elif next_answer_num > 0:

            b = copy.deepcopy(a)
            b = b[i+1:]
            next_all_nums = copy.deepcopy(all_nums)
            branch_sum_num += answer1(b, next_answer_num, next_all_nums, all_num_list)
        else:
            all_nums.pop(-1)
            continue
        all_nums.pop(-1)

    return branch_sum_num


def main():
    a = [1, 3, 4, 2, 6, 7, 5, 5, 8, 10, 9, 10, 7, 17]

    all_nums, all_num_list = list(), list()
    branch_sum_num = answer1(a, 29, all_nums, all_num_list)
    delete_index = list()
    for i in range(len(all_num_list)):
        for j in range(i + 1, len(all_num_list)):
            if operator.eq(all_num_list[i], all_num_list[j]):
                delete_index.append(j)

    delete_index = list(set(delete_index))
    delete_index.sort(reverse=True)

    for i in delete_index:
        all_num_list.pop(i)

    print('all_num_list', all_num_list)
    print(branch_sum_num - len(delete_index))

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Set;

public class testACM {

static Integer[] a = new Integer[20];
static int n;
static LinkedList<Integer> q = new LinkedList<Integer>();
static Set<LinkedList<Integer>> s = new HashSet<LinkedList<Integer>>();
public static void dfs(int index,int now) {
    if(index == n+1 || now > 29) {
        return;
    }
    now+=a[index];
    q.add(a[index]);
    if(now == 29) {
        s.add(q);        
        q.remove(q.size()-1);
        now-=a[index];
        dfs(index+1,now);
        return;
    }
    dfs(index+1,now);
    q.remove(q.size()-1);
    now-=a[index];
    dfs(index+1,now);

}

public static void main(String[] args) {
    Scanner reader = new Scanner(System.in);
    n = reader.nextInt();
    for(int i = 1; i<=n;i++) {
        int x = reader.nextInt();
        a[i] = Integer.valueOf(x);
    }
    dfs(1,0);
    System.out.println(s.size());
}

}

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
set<vector<int> >s;
int main()
{

    int a[] = {1, 3, 4, 2, 6,7,5,5,8,10,9,10,7,17};
    s.clear();
    int num = 0;
    for(int i = 1; i < (1 << 14); i++)
    {
        int sum = 0;
        vector<int>vet;
        vet.clear();
        for(int j = 0; j < 14; j++)
        {
            if(i & (1 << j))
            {
                sum += a[j];
                vet.push_back(a[j]);
            }
        }
        sort(vet.begin(), vet.end());
        if(sum == 29){
            s.insert(vet);

        }
    }
    set<vector<int> >::iterator it;
    for(it = s.begin(); it != s.end(); it++)
    {
        vector<int>vet;
        vet = *it;
        for(int i = 0, sz = vet.size(); i < sz; i++)printf("%d ", vet[i]);puts("");
    }
    printf("%d\n", s.size());
    return 0;
}