77. Combinations.md

77. Combinations

---

leetcode-cn Daily Challenge on September 8th, 2020.

---

Difficulty : Medium

Related Topics : Backtracking

---

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

---

Solution

• mine
  • Java
    • BFS Runtime: 13 ms, faster than 82.20%, Memory Usage: 47.8 MB, less than 35.35% of Java online submissions

      public List<List<Integer>> combine(int n, int k) {
          List<List<Integer>> res = new ArrayList<>();
          if(k == 0) return res;
      
          LinkedList<LinkedList<Integer>> list = new LinkedList<>();
          for(int i = 1; i <= n; i++){
              list.add(new LinkedList<>(Arrays.asList(i)));
          }
          while(!list.isEmpty()){
              if (list.getFirst().size() == k){
                  res.addAll(list);
                  break;
              }
              LinkedList<Integer> first = list.removeFirst();
              int end = first.getLast();
              //skip the less than k case
              if(end + (k - first.size()) > n) continue;
              for(int i = end + 1; i <= n; i++){
                  LinkedList<Integer> t = new LinkedList<>();
                  t.addAll(first);
                  t.add(i);
                  list.add(t);
              }
          }
          return res;
      }
      

---

• the most votes

• Backtracking Runtime: 17 ms, faster than 75.13%, Memory Usage: 40.7 MB, less than 77.36% of Java online submissions

  public static List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> combs = new ArrayList<List<Integer>>();
      combine(combs, new ArrayList<Integer>(), 1, n, k);
      return combs;
  }
  
  public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
      if (k == 0) {
          combs.add(new ArrayList<Integer>(comb));
          return;
      }
      for (int i = start; i <= n; i++) {
          comb.add(i);
          combine(combs, comb, i + 1, n, k - 1);
          comb.remove(comb.size() - 1);
      }
  }
  

---