@@ -0,0 +1,1631 @@
+/***%0A * 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.%0A *%0A * Each number in C may only be used once in the combination.%0A *%0A * Note:%0A * All numbers (including target) will be positive integers.%0A * Elements in a combination (a1, a2, %E2%80%A6 , ak) must be in non-descending order. (ie, a1 %E2%89%A4 a2 %E2%89%A4 %E2%80%A6 %E2%89%A4 ak).%0A * The solution set must not contain duplicate combinations.%0A * For example, given candidate set 10,1,2,7,6,1,5 and target 8, %0A * A solution set is: %0A * %5B1, 7%5D %0A * %5B1, 2, 5%5D %0A * %5B2, 6%5D %0A * %5B1, 1, 6%5D %0A */%0Aimport java.util.ArrayList;%0A%0Apublic class Solution %7B%0A    // O(n!) O(n)%0A    public ArrayList%3CArrayList%3CInteger%3E%3E combinationSum2(int%5B%5D candidates, int target) %7B%0A        ArrayList%3CArrayList%3CInteger%3E%3E ret = new ArrayList%3CArrayList%3CInteger%3E%3E();%0A        ArrayList%3CInteger%3E comb = new ArrayList%3CInteger%3E();%0A        Arrays.sort(candidates);%0A        dfs(candidates, target, ret, comb, 0);%0A        return ret;%0A    %7D%0A%0A    private void dfs(int%5B%5D candidates, int gap, ArrayList%3CArrayList%3CInteger%3E%3E ret, ArrayList%3CInteger%3E path, int k) %7B%0A        if (gap == 0) %7B%0A            ArrayList%3CInteger%3E newpath = new ArrayList%3CInteger%3E(path);%0A            ret.add(newpath);%0A            return;%0A        %7D%0A        for (int i = k, c = 0; i %3C candidates.length; i++, c++) %7B%0A            if (gap %3C candidates%5Bi%5D) return;%0A            if (i %3E 0 && c %3E 0 && candidates%5Bi%5D == candidates%5Bi - 1%5D) continue;%0A            path.add(candidates%5Bi%5D);%0A            dfs(candidates, gap - candidates%5Bi%5D, ret, path, i + 1);%0A            path.remove(path.size() - 1);%0A        %7D%0A    %7D%0A%7D%0A

add CombinationSumII.java