某实习生招聘

看到题目，很显然是0,1背包问题,苦于平时练手不多，在正在开始写的时候犯难了，调试不通过，导致在规定的时间没提交，后悔不已。之后自己解决了代码问题，做个记录。

题目:给定数组{1,3,4,5,9,11,2},输出和为n的组合个数

分析:常规题目一般我给定连续的数组，如{1,2,3,4,5...,k}，输出何为n的组合个数，而题目给定的数组非连续，因此在递归代码中势必需要有个中间flag用来记录选取信息。

直接贴自己写的java代码（没提交好遗憾）

import java.util.HashMap;import java.util.Scanner;public class Sum {	static int length;	static int[] value = {1,3,4,5,9,11,2};	static HashMap<Integer,Integer> flag = new HashMap<Integer,Integer>();		static int count = 0;    static void findCombination(int sum,int index){        if (index<0||sum<0) {            return;        }        if (value[index]==sum) {            flag.put(value[index], 1);            for(Integer key:flag.keySet())            	if(flag.get(key)==1){            		System.out.PRint(key+" ");            		            	}            flag.put(value[index],0);            count++;            System.out.println();        }        flag.put(value[index], 1);        findCombination(sum-value[index],index-1);        flag.put(value[index], 0);        findCombination(sum,index-1);    }    public static void main(String[] args) {        /*int n,m;        Scanner s=new Scanner(System.in);        n=s.nextInt();*/        int n=4;        flag.put(1, 0);        flag.put(3, 0);        flag.put(4, 0);        flag.put(5, 0);        flag.put(9, 0);        flag.put(11, 0);        flag.put(2, 0);        findCombination(n,6);        System.out.println(count);    }}