import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Solution {
    public static void main(String[] args) {
        List<List<Integer>> combos = combinationSum(new int[] { 8, 7, 4, 3 }, 11);

        for (List<Integer> combo : combos) {
            System.out.println(combo);
        }
    }

    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        int[] candidatesCopy = candidates.clone();
        Arrays.sort(candidatesCopy);

        Boolean[][] cache = new Boolean[target + 1][candidates.length];
        boolean works = combinationSum(candidatesCopy, target, 0, cache);
        List<List<Integer>> results = new ArrayList<>();

        if (!works) {
            return results;
        }

        generateSumOptions(candidatesCopy, target, 0, cache, results, new Stack<Integer>());

        return results;
    }

    private static boolean combinationSum(int[] candidates, int target, int denominationIndex, Boolean[][] cache) {
        if (target < 0) {
            return false;
        }

        if (target == 0) {
            return true;
        }

        if (denominationIndex == candidates.length) {
            return false;
        }

        if (cache[target][denominationIndex] != null) {
            return cache[target][denominationIndex];
        }

        if (denominationIndex > 0 && candidates[denominationIndex] == candidates[denominationIndex - 1]) {
            cache[target][denominationIndex] = combinationSum(candidates, target, denominationIndex + 1, cache);
            return cache[target][denominationIndex];
        }

        boolean withCurrentElement = combinationSum(candidates, target - candidates[denominationIndex], denominationIndex, cache);
        boolean withoutCurrentElement = combinationSum(candidates, target, denominationIndex + 1, cache);

        cache[target][denominationIndex] = withCurrentElement || withoutCurrentElement;

        return cache[target][denominationIndex];
    }

    private static void generateSumOptions(int[] candidates, int target, int denominationIndex, Boolean[][] cache, List<List<Integer>> results, Stack<Integer> currentResult) {
        if (target < 0) {
            return;
        }

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

        if (denominationIndex == candidates.length) {
            return;
        }

        if (!cache[target][denominationIndex]) {
            return;
        }

        currentResult.push(candidates[denominationIndex]);
        generateSumOptions(candidates, target - candidates[denominationIndex], denominationIndex, cache, results, currentResult);
        currentResult.pop();

        generateSumOptions(candidates, target, denominationIndex + 1, cache, results, currentResult);
    }
}