LeetCode 77. Combinations

Question

Given two integers n and k, return all possible combinations of k numbers out of the range [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

Source: https://leetcode.com/problems/combinations/

Solution

The following code is based on the append solution of LeetCode 47. Permutations II. Why not swap-based solution? Because available elements in this question are not a fixed set but can be different subsets of [1, n].

Because combinations do not care about order, we can get combinations by restricting permutations to an ascending order. It is ok if the value on current position is too large to leave enough space for deeper layers. DFS paths just safely return to last layer before reach kth layer (leave layer).

// start is the smallest valid value for current position
private void dfs(int n, int k, int start, LinkedList<Integer> current, List<List<Integer>> result) {
    if (current.size() == k) {
        List<Integer> copy = new ArrayList<>(current);
        result.add(copy);
        return;
    }

    // combinations do not care about order
    // we can get combinations by restricting permutations to an ascending order
    // it is ok if the value on current position is too large to leave enough space for deeper layers
    // dfs paths just safely return to last layer before reach kth layer (leave layer)
    for (int i = start; i <= n; i++) {
        current.addLast(i);
        dfs(n, k, i + 1, current, result);
        current.removeLast();
    }
}

public List<List<Integer>> combine(int n, int k) {
    LinkedList<Integer> comb = new LinkedList<>();
    List<List<Integer>> combines = new ArrayList<>();
    dfs(n, k, 1, comb, combines);
    return combines;
}