/*
Runtime: 13 ms, faster than 8.96% of Java online submissions for Combination Sum.
Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Combination Sum.
*/
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> results = new ArrayList<List<Integer>>();

        if (target == 0){
            results.add(new ArrayList<Integer>());
        }

        int sum;
        int[] counts = new int[candidates.length];
        int currentLead = 0;

        while (currentLead < candidates.length) {
            counts[currentLead]++;

            sum = 0;
            for (int i = 0; i < candidates.length; i++) {
                sum += candidates[i] * counts[i];
            }

            if (sum == target) {
                List<Integer> currentResult = new ArrayList<Integer>();

                for (int i = 0; i < candidates.length; i++) {
                    for (int j = 0; j < counts[i]; j++) {
                        currentResult.add(candidates[i]);
                    }
                }

                results.add(currentResult);
            }

            if (sum >= target) {
                counts[currentLead] = 0;
                currentLead++;
            }
            else {
                currentLead = 0;
            }
        }


        return results;
    }
}