[LeetCode] 77. Combinations

Posted on | In

Problem

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

Example:

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Explanation

  1. When $n = 4$ and $k = 2$, we can only have two numbers in the sublist. If for the first number we choose $1$, then the second number we can have $2$, $3$, $4$. If for the first number we choose $3$, we can only have $4$ as the second number.

  2. We can see that we need to use iteration to choose the first number, then for the second number, we start looping from the first number plus one.

  3. So, we need to have a start variable, result, temp, n and k variables.

  4. The base case is whenever the temp variable already have $k$ numbers, we return.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    void dfs(int n, int k, int start, List<Integer> temp, List<List<Integer>> res) {
        if (temp.size() == k) {
            res.add(new ArrayList<Integer>(temp));
            return;
        }
        for (int i = start; i <= n; i++) {
            temp.add(i);
            dfs(n, k, i+1, temp, res);
            temp.remove(temp.size()-1);
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        List<Integer> temp = new ArrayList<Integer>();
        dfs(n, k, 1, temp, res);
        return res;
    }
}