Combinations

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

For example,

If n = 4 and k = 2, a solution is:

  1. [
  2.   [2,4],
  3.   [3,4],
  4.   [2,3],
  5.   [1,2],
  6.   [1,3],
  7.   [1,4],
  8. ]

Solution:

  1. public class Solution {
  2.   public List<List<Integer>> combine(int n, int k) {
  3.     List<List<Integer>> res = new ArrayList<>();
  4.     List<Integer> sol = new ArrayList<>();
  6.     helper(n, k, 1, sol, res);
  8.     return res;
  9.   }
  11.   void helper(int n, int k, int m, List<Integer> sol, List<List<Integer>> res) {
  12.     if (sol.size() == k) {
  13.       res.add(new ArrayList<Integer>(sol));
  14.       return;
  15.     }
  17.     for (int i = m; i <= n; i++) {
  18.       sol.add(i);
  19.       helper(n, k, i + 1, sol, res);
  20.       sol.remove(sol.size() - 1);
  21.     }
  22.   }
  23. }