LeetCode Combinations (JavaScript), Backtracking

링크 : https://leetcode.com/problems/combinations/description/

문제 설명

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

---

문제 풀이

1. 일반 DFS를 통한 풀이

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const answer = [];

    const findNums = (arr) => {
        if (arr.length === k) {
            answer.push(arr);
            return;
        }

        for (let i = arr[arr.length - 1] + 1; i <= n; i++) {
            findNums([...arr, i]);
        }
    }

    for (let i = 1; i <= n; i++) {
        findNums([i]);
    }

    return answer;
};

 

2. Backtracking을 통한 풀이

일반 DFS를 통한 풀이에서 findNums를 하는 과정에서 arr을 계속해서 복제하는 로직으로 매번 새로운 배열을 생성 -> 배열을 복사하는 과정이 O(n)의 시간복잡도를 가지기 때문에 이를 좀 더 효율적으로 만들기 위해 Backtracking을 사용

 

접근 방식

- Backtracking을 이용하여 매번 배열을 생성하지 않고 하나의 배열을 통해 답을 구하도록 함.

- 따라서 배열을 생성하는 부분이 없으므로 시간복잡도 측면에서 더 효율적임.

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const answer = [];
    const comb = [];

    const backtracking = (index) => {
        if (comb.length === k) {
            answer.push([...comb]);
            return;
        }

        for (let i = index; i <= n; i++) {
            comb.push(i);
            backtracking(i + 1);
            comb.pop();
        }
    }

    backtracking(1);

    return answer;
};

---

결론

일반 dfs를 좀 더 효율적으로 만들 수 있는 방식도 고민하면 좋을 것 같다.