LeetCode - 조합

문제 설명

두 정수 n과 k가 주어지면 [1, n] 범위를 벗어나는 k 숫자의 모든 가능한 조합을 반환합니다.

어떤 순서로든 답변을 반환할 수 있습니다.

다음에서 가져온 문제 설명: https://leetcode.com/problems/combinations/ .

예 1:

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

예 2:

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

제약:

- 1 <= n <= 20
- 1 <= k <= n

설명

무차별 대입 솔루션

무차별 대입 방식은 크기의 가능한 모든 조합을 생성하는 것입니다.
k는 n개의 요소입니다.
이 접근법은 우리가 n을 증가시킬 때 많은 시간을 소비할 것입니다.

역추적

최적화된 솔루션은 역추적 접근 방식을 사용하는 것입니다.
current라는 임시 배열을 만듭니다.
그리고
현재 배열의 크기가 다음과 같을 때까지 요소를 계속 추가합니다.
케이.

한계 k에 도달하면 마지막 요소를 팝합니다.
그리고
다음 요소를 밀어 넣습니다. n에 도달할 때까지 동일한 단계를 반복합니다.

이 공식을 어떻게 사용할 수 있는지 알아보기 위해 알고리즘을 확인해 봅시다.

// combine(n, k)
- initialize result, current

- backtrack(result, current, n, k, 0)

- return result

// backtrack(result, current, n, k, pos)
- if current.size() == k
  - result.push_back(current)
  - return

- loop for i = pos; i < n; i++
  - current.push_back(i + 1)
  - backtrack(result, current, n, k, i + 1)
  - current.pop_back()

C++, Golang 및 Javascript의 솔루션을 확인해 봅시다.

C++ 솔루션

class Solution {
public:
    void backtrack(vector<vector<int>> &result, vector<int> current, int n, int k, int pos) {
        if(current.size() == k) {
            result.push_back(current);
            return;
        }

        for(int i = pos; i < n; i++) {
            current.push_back(i + 1);
            backtrack(result, current, n, k, i + 1);
            current.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> current;

        backtrack(result, current, n, k, 0);

        return result;
    }
};

골랑 솔루션

func backtrack(result *[][]int, current []int, n, k, pos int) {
    if len(current) == k {
        *result = append(*result, append([]int{}, current...))
        return
    }

    for i := pos; i < n; i++ {
        current = append(current, i + 1)
        backtrack(result, current, n, k, i + 1)
        current = current[:len(current) - 1]
    }
}

func combine(n int, k int) [][]int {
    result := make([][]int, 0)

    backtrack(&result, []int{}, n, k, 0)

    return result
}

자바스크립트 솔루션

var combine = function(n, k) {
    let result = [];

    const backtrack = (pos, n, k, current) => {
        if(current.length === k){
            result.push([...current]);
        }

        if(pos > n){
            return;
        }
        for(let i = pos; i <= n; i++){
            current.push(i);
            backtrack(i + 1, n, k, current);
            current.pop();
        }
    }

    backtrack(1, n, k, []);

    return result;
};

솔루션이 어떻게 작동하는지 알아보기 위해 알고리즘을 시험 실행해 보겠습니다.

Input: n = 3, k = 2

// combine function
Step 1: vector<vector<int>> result
        vector<int> current

Step 2: backtrack(result, current, n, k, 0)
        backtrack([[]], [], 3, 2, 0)

// backtrack function
Step 3: current.size() == k
        0 == 2
        false

        loop for i = pos; i < n;
          i = 0
          0 < 3
          true

          current.push_back(i + 1)
          current.push_back(0 + 1)
          current.push_back(1)

          current = [1]

          backtrack(result, current, n, k, i + 1)
          backtrack([[]], [1], 3, 2, 0 + 1)
          backtrack([[]], [1], 3, 2, 1)

Step 4: current.size() == k
        1 == 2
        false

        loop for i = pos; i < n;
          i = 1
          1 < 3
          true

          current.push_back(i + 1)
          current.push_back(1 + 1)
          current.push_back(2)

          current = [1, 2]

          backtrack(result, current, n, k, i + 1)
          backtrack([[]], [1, 2], 3, 2, 1 + 1)
          backtrack([[]], [1, 2], 3, 2, 2)

Step 5: current.size() == k
        2 == 2
        true

        result.push_back(current)
        result.push_back([1, 2])

        result = [[1, 2]]
        return

        We backtrack to step 4 and move to the next step.

Step 6: current.pop_back()
        current = [1, 2]

        current = [1]

        i++
        i = 2

        loop for i = pos; i < n;
          i = 2
          2 < 3
          true

          current.push_back(i + 1)
          current.push_back(2 + 1)
          current.push_back(3)

          current = [1, 3]

          backtrack(result, current, n, k, i + 1)
          backtrack([[1, 2]], [1, 3], 3, 2, 2 + 1)
          backtrack([[1, 2]], [1, 3], 3, 2, 3)

Step 7: current.size() == k
        2 == 2
        true

        result.push_back(current)
        result.push_back([1, 3])

        result = [[1, 2], [1, 3]]
        return

        We backtrack to step 6 and move to the next step.

Step 8: current.pop_back()
        current = [1, 3]

        current = [1]

        i++
        i = 3

        loop for i = pos; i < n;
          i = 3
          3 < 3
          false

        We backtrack to step 3 and move to the next step.

Step 9: current.pop_back()
        current = [1]

        current = []

        i++
        i = 1

        loop for i = pos; i < n;
          i = 1
          1 < 3
          true

          current.push_back(i + 1)
          current.push_back(1 + 1)
          current.push_back(2)

          current = [2]

          backtrack(result, current, n, k, i + 1)
          backtrack([[1, 2], [1, 3]], [2], 3, 2, 1 + 1)
          backtrack([[1, 2], [1, 3]], [2], 3, 2, 2)

Step 10: current.size() == k
         1 == 2
         false

         loop for i = pos; i < n;
           i = 2
           2 < 3
           true

           current.push_back(i + 1)
           current.push_back(2 + 1)
           current.push_back(3)

           current = [2, 3]

           backtrack(result, current, n, k, i + 1)
           backtrack([[1, 2], [1, 3]], [2, 3], 3, 2, 2 + 1)
           backtrack([[1, 2], [1, 3]], [2, 3], 3, 2, 3)

Step 11:  current.size() == k
          2 == 2
          true

          result.push_back(current)
          result.push_back([2, 3])

          result = [[1, 2], [1, 3], [2, 3]]
          return

          We backtrack to step 10 and move to the next step.

Step 12: current.pop_back()
         current = [2, 3]

         current = [2]

         i++
         i = 3

         loop for i = pos; i < n;
           i = 3
           3 < 3
           false

         We backtrack to step 9

Step 13: current.pop_back()
         current = [2]

         current = []

         i++
         i = 3

         loop for i = pos; i < n;
           i = 3
           3 < 3
           false

        We backtrack to combine function and return result

// combine function
Step 14: return result

So we return the result as [[1, 2], [1, 3], [2, 3]]