gistfile1.txt

import java.util.ArrayList;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] combi = createCombination(candidates, target);
        ArrayList<ArrayList<Integer>>[][] S = new ArrayList<ArrayList<Integer>>[combi.length][target + 1];
        for (int i = 0; i < combi.length; i++) {
            for (int t = 1; t <= target; t++) {
                ArrayList<ArrayList<Integer>> local = new ArrayList<>();
                S[i][t] = local;
                if (combi[i] == t) {
                    local.add(new ArrayList<Integer>(Arrays.asList(t)));
                } else if (t >= combi[i] && !(S[i-1][t - combi[i]]).isEmpty()){
                    ArrayList<ArrayList<Integer>> prev = S[i-1][t - combi[i]];
                    for (ArrayList<Integer> ls: prev) {
                        ArrayList<Integer> newList = new ArrayList<>(ls);
                        newList.add(combi[i]);
                        
                        local.add(newList);
                    }
                }
            }
        }
    }
    
    public int[] createCombination(int[] candidates, int target) {
        ArrayList<Integer> ls = new ArrayList<>();
        for (int i: candidates) {
            int num = target / i;
            for (int k = 0; k < num; k++) ls.add(i);
        }
        
        return ls.stream().mapToInt(k -> k).toArray();
    }
    
    
}