给定一个array和一个固定值sum,

给 定一个array和一个固定值sum,
找出array中加和等于sum的最少元素个数
array中肯定有{1}这个元素，除了{1}这个元素只能用一次意外，其他元素可以重复使用

例如 arr={90，30，18，15，10，5,3，2,1} sum=32
则返回2， 即最小的组合是两个数{30,2}

Java version:

public int solve(int[] a, int sum) {
        HashSet<Integer> set = new HashSet<Integer>();
        for (int i : a) set.add(i);
        set.remove(1);
        
        int[] m = new int[sum+1];
        m[1] = 1;
        for (int i=2; i<=sum; i++) {
            m[i] = sum+1;
            for (int j : set) {
                if (j<=i) m[i] = Math.min(m[i], 1+m[i-j]);
            }
        }
        
        return m[sum];
    }


带输出的，不用分配那么多空间，只要记住parent index就行。

public int solve2(int[] a, int sum) {
        ArrayList<Integer> numbers = new ArrayList<Integer>();
        for (int i : a) if (i!=1) numbers.add(i);
        
        int[][] m = new int[sum+1][2];
        m[0] = new int[]{0, -1};
        m[1] = new int[]{1, 0};
        for (int i=2; i<=sum; i++) {
            m[i] = new int[]{sum+1, -1};
            for (int j : numbers) {
                if (j<=i && m[i][0] > 1+m[i-j][0]) {
                    m[i][0] = 1+m[i-j][0];
                    m[i][1] = i - j;
                }
            }
        }
        
        print(m, sum);
        return m[sum][0];
    }
    
    private void print(int[][] m, int sum) {
        for (int i=sum; i>0; ) {
            System.out.print(i - m[i][1] + " ");
            i = m[i][1];
        }
        System.out.println();
    }