Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is:

[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

Solution

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {

     List<List<Integer>> result = new ArrayList<List<Integer>>();
        combination(candidates, target, 0, -1, new ArrayList<Integer>(), result);

        List<List<Integer>> finalResult = new ArrayList<List<Integer>>();
        for (List<Integer> indices : result) {
            List<Integer> temp = new ArrayList<Integer>();
            for (Integer item : indices) {
                temp.add(candidates[item]);
            }

            boolean flag = true;
            for (List<Integer> ls : finalResult) {
                if (compare(ls, temp)) {
                    flag = false;
                    break;
                }
            }

            if (flag) {
                Collections.sort(temp);
                finalResult.add(temp);
            }
        }

        return finalResult;
    }

    public static void combination(int[] candidates, int target, int value, int index, List<Integer> currentSolution, List<List<Integer>> solutions) {
        if (value > target) {
            return;
        }

        if (value == target) {
            for (List<Integer> each : solutions) {
                if (compare(each, currentSolution)) {
                    return;
                }
            }

            solutions.add(new ArrayList<Integer>(currentSolution));
            return;
        }

        for (int i = index + 1; i < candidates.length; i++) {
            currentSolution.add(i);
            combination(candidates, target, value + candidates[i], i, currentSolution, solutions);
            currentSolution.remove(currentSolution.size() - 1);
        }

    }

    public static boolean compare(List<Integer> lst1o, List<Integer> lst2o) {
        List<Integer> lst1 = new ArrayList<Integer>(lst1o);
        List<Integer> lst2 = new ArrayList<Integer>(lst2o);

        if (lst1.size() != lst2.size()) {
            return false;
        }

        Collections.sort(lst1);
        Collections.sort(lst2);

        for (int i = 0; i < lst1.size(); i++) {
            if (!lst1.get(i).equals(lst2.get(i)))
                return false;
        }

        return true;
    }
}