/ Data Structure and Algorithms  

Leetcode 77. Combinations

Question



Given n, k, select k numbers from {1, 2, 3 ... n}, output all possible, and sort numbers from small to large, and each number can only be used once.

Similar Questions

Solution

Very classic backtracking problem. First select a number, then enter the recursion to continue to select, meet the conditions and add to the result, then back to the previous step and continue the recursion.

Look at the code directly, it is easy to understand.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(result, new ArrayList<>(), n, k, 1);

    return result;
}

// similar to permutation
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
    // find a solution, add to result list
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }

    for (int i = start; i <= n; i++) {
        // avoid duplicates
        if (tempList.contains(i)) {
            continue;
        }

        // add current number in
        tempList.add(i);

        // add other numbers in
        backtrack(result, tempList, n, k, i + 1);

        // all possible number has been added, remove last number and start
        tempList.remove(tempList.size() - 1);
    }
}

A for loop, add, recurse, delete, is a classic backtracking template. Here is an optimization method. In the for loop, i goes from start to n, but it is not necessary to go to n. For example, n = 5, k = 4, tempList.size () == 1, which means that we need (4-1 = 3) numbers. If i = 4, we will at most add 4 and 5 to tempList. In this case, tempList.size() is equal to 1 + 2 = 3, which is less than 4, so i does not need to be equal to 4, and it is sufficient for i to loop to 3.

So the end condition of the for loop can be changed to i <= n-(k-tempList.size()) + 1, k-tempList.size() represents the numbers we need. Because we got n in the end, we need to add 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> result = new ArrayList<>();

    backtrack(result, new ArrayList<>(), n, k, 1);

    return result;
}

// similar to permutation
private void backtrack(List<List<Integer>> result, List<Integer> tempList, int n, int k, int start) {
    // find a solution, add to result list
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }

    for (int i = start; i <= n - (k -tempList.size()) + 1; i++) {
        // avoid duplicates
        if (tempList.contains(i)) {
            continue;
        }

        // add current number in
        tempList.add(i);

        // add other numbers in
        backtrack(result, tempList, n, k, i + 1);

        // all possible number has been added, remove last number and start
        tempList.remove(tempList.size() - 1);
    }
}

Although only one line of code is changed, the speed is much faster.

There are other methods, such as recursion, iteration, dynamic programming can be applied here, which I will be discuss in the future if have time.