ass Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
       List<List<Integer>> ans = new ArrayList<List<Integer>>();
       List<Integer> cur = new ArrayList<>();
       Arrays.sort(candidates);
       for (int n = 1; n <= target / candidates[0]; ++n) {
           dfs(candidates, target, 0, 0, n, cur, ans);
       }
       return ans;
    }
    void dfs(int[] candidates, int target, int s, int d, int n, List<Integer> cur, List<List<Integer>> ans) {
        if (d == n) {
            if (target == 0) {
                ans.add(new ArrayList<Integer>(cur)); //一定要copy
            }
            return;
        }
        for (int i = s; i < candidates.length; ++i) {
            if (candidates[i] > target){
                break;
            }
            cur.add(candidates[i]);
            dfs(candidates, target - candidates[i], i, d + 1, n, cur, ans);
            cur.remove(cur.size() - 1);
        }
    }
}

@@ -1,8 +1,203 @@
+// Solution: DFS%0A// Time complexity: O(2%5En) let s = target / min(nums%5Bi%5D) T = c(s, 1) + c(s, 2) + ... + c(s, s) = 2%5Es%0A// Space complexity: O(n) O(target / min(nums%5Bi%5D))%0A// %E8%BE%93%E5%87%BA%E9%A1%BA%E5%BA%8F%E4%BB%8E%E5%B0%8F%E7%9A%84%E9%95%BF%E5%BA%A6%E4%B8%AA%E6%95%B0%E5%88%B0%E5%A4%A7%E7%9A%84%E9%95%BF%E5%BA%A6%E4%B8%AA%E6%95%B0%E6%8E%92%E5%BA%8F%0Acl
 ass Solu
@@ -481,17 +481,16 @@
 %5D; ++n) 
-%7B
 %0A       
@@ -537,25 +537,16 @@
 , ans);%0A
-       %7D%0A
        r
@@ -554,17 +554,16 @@
 turn ans
-;
 %0A    %7D%0A 
@@ -565,16 +565,24 @@
   %7D%0A    
+private 
 void dfs
@@ -733,26 +733,8 @@
 = 0)
- %7B%0A               
  ans
@@ -778,30 +778,16 @@
 %E4%B8%80%E5%AE%9A%E8%A6%81copy%0A
-            %7D%0A
         
@@ -800,32 +800,41 @@
 turn;%0A        %7D%0A
+        %0A
         for (int
@@ -914,46 +914,15 @@
 get)
-%7B%0A                break;%0A            %7D
+ break;
 %0A   
@@ -1088,8 +1088,965 @@
     %7D%0A%7D%0A
+%0A// // Solution: DFS%0A// // %E8%BE%93%E5%87%BA%E7%9A%84%E9%95%BF%E5%BA%A6%E9%A1%BA%E5%BA%8F%E4%B8%8D%E6%98%AF%E4%BB%8E%E5%B0%8F%E5%88%B0%E5%A4%A7%0A// // Time complexity: O(2%5En)%0A// // Space complexity: O(n)%0A// class Solution %7B%0A//     public List%3CList%3CInteger%3E%3E combinationSum(int%5B%5D candidates, int target) %7B%0A//         List%3CList%3CInteger%3E%3E ans = new ArrayList%3CList%3CInteger%3E%3E();%0A//         List%3CInteger%3E cur = new ArrayList%3CInteger%3E();%0A//         Arrays.sort(candidates);%0A//         dfs(candidates, target, 0, cur, ans);%0A//         return ans;%0A//     %7D%0A//     private void dfs(int%5B%5D candidates, int target, int s, List%3CInteger%3E cur, List%3CList%3CInteger%3E%3E ans) %7B%0A//         if (target == 0) %7B%0A//             ans.add(new ArrayList%3CInteger%3E(cur));%0A//             return;%0A//         %7D%0A//         for (int i = s; i %3C candidates.length; ++i) %7B%0A//             if (candidates%5Bi%5D %3E target) break;%0A//             cur.add(candidates%5Bi%5D);%0A//             dfs(candidates, target - candidates%5Bi%5D, i, cur, ans);%0A//             cur.remove(cur.size() - 1);%0A//         %7D%0A//     %7D%0A// %7D%0A%0A%0A

add CombinationSum.java