Combination Sum II

combination.java

// https://www.interviewbit.com/problems/combination-sum-ii/

import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Solution x = new Solution();
        int[] input = new int[]{10,1,2,7,6,1,5};
        x.combinationSum(input, 8);
    }

    public Set<List<Integer>> combinationSum(int[] candidates, int target) {
        Set<List<Integer>> results = new HashSet<List<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return results;
        }

        Arrays.sort(candidates);

        List<Integer> combination = new ArrayList<Integer>();
        toFindCombinationsToTarget(results, combination, candidates, target, 0);

        System.out.println(results);
        return results;
    }

    private void toFindCombinationsToTarget(Set<List<Integer>> results, List<Integer> combination, int[] candidates, int target, int startIndex) {
        if (target == 0) {
            results.add(new ArrayList<Integer>(combination));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            if (candidates[i] > target) {
                break;
            }

            combination.add(candidates[i]);
            toFindCombinationsToTarget(results, combination, candidates, target - candidates[i], i+1);
            combination.remove(combination.size() - 1);
        }
    }
}