Jan 16 - Combination Sum; Array; BackTracking;

public class Solution {
    public List<Integer> listSum;
    public List<List<Integer>> list;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        listSum = new ArrayList<>();
        list = new ArrayList<>();
        List<List<Integer>> resultList = new ArrayList<>();
        int len = candidates.length;
        if(len == 0) return resultList;
        for(int i = 0; i < len; i++){
            int digit = candidates[i];
            if(digit > target) break;
            resultList = traverseArray(resultList, digit, target);
        }
        return resultList;
        
    }
    
    public List<List<Integer>> traverseArray(List<List<Integer>> resultList, int digit, int target){
        List<Integer> sum = new ArrayList<>();
        List<List<Integer>> list_combination = new ArrayList<>();
        int n_digit = digit;
        int count = 0;
        while(n_digit < target){
            count++;
            List<Integer> combination = new ArrayList<>();
            for(int i = 0; i < count; i++) combination.add(digit);
            list_combination.add(combination);
            sum.add(n_digit);
            n_digit += digit;
        }
        if(n_digit == target){
            List<Integer> oneDigitCombination = new ArrayList<>();
            for(int i = 1; i <= count+1; i++) oneDigitCombination.add(digit);
            resultList.add(oneDigitCombination);
        }
        
        if(listSum.size() == 0){
            listSum = sum;
            list = list_combination;
            return resultList;
        }
        int list_sum_length = listSum.size();
        for(int j = 0; j < list_sum_length; j++){
            List<Integer> c1 = list.get(j);
            
            for(int k = 0; k < count; k++){
                int t = listSum.get(j) + sum.get(k);
                List<Integer> c2 = list_combination.get(k);
                if(t < target){
                    listSum.add(t);
                    List<Integer> l = new ArrayList<>();
                    for(int i = 0; i < c1.size(); i++) l.add(c1.get(i));
                    for(int i = 0; i < c2.size(); i++) l.add(c2.get(i));
                    list.add(l);
                }
                if(t == target){
                    List<Integer> l = new ArrayList<>();
                    for(int i = 0; i < c1.size(); i++) l.add(c1.get(i));
                    for(int i = 0; i < c2.size(); i++) l.add(c2.get(i));
                    resultList.add(l);
                }
            }
        }
        for(int j = 0; j < count; j++){
            listSum.add(sum.get(j));
            list.add(list_combination.get(j));
        }
        return resultList;
        
        
    }
}