@@ -0,0 +1,2491 @@
+/***%0A * Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.%0A *%0A * The same repeated number may be chosen from C unlimited number of times.%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 2,3,6,7 and target 7, %0A * A solution set is: %0A * %5B7%5D %0A * %5B2, 2, 3%5D %0A */%0Aimport java.util.ArrayList;%0A%0Apublic class Solution %7B%0A    // Solution 1: O(n!) O(n)%0A    /*%0A    public ArrayList%3CArrayList%3CInteger%3E%3E combinationSum(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 target, ArrayList%3CArrayList%3CInteger%3E%3E ret, ArrayList%3CInteger%3E path, int k) %7B%0A        int sum = 0;%0A        for (int i : path)%0A            sum += i;%0A        if (sum %3E target)   return;%0A        else if (sum == target) %7B%0A            ArrayList%3CInteger%3E newpath = new ArrayList%3CInteger%3E(path);%0A            ret.add(newpath);%0A            return;%0A        %7D%0A        for (int i = k; i %3C candidates.length; i++) %7B%0A            path.add(candidates%5Bi%5D);%0A            dfs(candidates, target, ret, path, i);%0A            path.remove(path.size() - 1);%0A        %7D%0A    %7D%0A    */%0A%0A    // Solution 2: O(n!) O(n)%0A    public ArrayList%3CArrayList%3CInteger%3E%3E combinationSum(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; i %3C candidates.length; i++) %7B%0A            if (gap %3C candidates%5Bi%5D) return;%0A%0A            path.add(candidates%5Bi%5D);%0A            dfs(candidates, gap - candidates%5Bi%5D, ret, path, i);%0A            path.remove(path.size() - 1);%0A        %7D%0A    %7D%0A%7D%0A

add CombinationSum.java