MEDIUM/src/medium/Combinations.java

fishercoder1534 · fishercoder1534 · commit aa68be3c0d33 · 2016-09-13T12:15:08.000-07:00
diff --git a/MEDIUM/src/medium/Combinations.java b/MEDIUM/src/medium/Combinations.java
@@ -0,0 +1,31 @@
+package medium;
+import java.util.*;
+
+public class Combinations {
+    //I'm glad that I made this one AC'ed the first time I submitted it.
+    //After finishing three similar problems! Cool!
+
+    public List<List<Integer>> combine(int n, int k) {
+        List<List<Integer>> result = new ArrayList();
+        int[] nums = new int[n];
+        for(int i = 0; i < n; i++){
+            nums[i] = i+1;
+        }
+        backtracking(k, 0, nums, new ArrayList(), result);
+        return result;
+    }
+    
+    void backtracking(int k, int start, int[] nums, List<Integer> temp, List<List<Integer>> result){
+        if(temp.size() == k){
+            List<Integer> newTemp = new ArrayList(temp);
+            result.add(newTemp);
+        } else if(temp.size() < k){
+            for(int i = start; i < nums.length; i++){
+                temp.add(nums[i]);
+                backtracking(k, i+1, nums, temp, result);
+                temp.remove(temp.size()-1);
+            }
+        }
+    }
+
+}
