[77. Combinations](https://leetcode.com/problems/combinations/)

### 題目描述

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` <= 201 <= n <= 20
1 <= k <= n
* 1 <= k <= n

### 解答

#### C++

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> subAns;
        vector<vector<int>> ans;
        backtrack(n, k, 1, subAns, ans);
        return ans;
    }

    void backtrack(int n, int k, int first, vector<int>& subAns, vector<vector<int>>& ans) {
        if (subAns.size() == k) {
            ans.push_back(subAns);
            return ;
        }

        for (int i = first; i <= n; i ++) {
            subAns.push_back(i);
            backtrack(n, k, i + 1, subAns, ans);
            subAns.pop_back();
        }
    }
};

> [name=Jerry Wu][time=1 August, 2023]

#### Python
內建作弊一下XD

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(combinations(range(1, n + 1), k))

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtrack(i, arr):
            if len(arr) == k:
                res.append(arr.copy())
                return
            
            for i in range(i, n + 1):
                arr.append(i)
                backtrack(i + 1, arr)
                arr.pop()

        backtrack(1, [])
        return res

> [name=Ron Chen][time=Tue, Aug 1, 2023]

#### TypeScript

function combine(n: number, k: number): number[][] {
  const result: number[][] = [];
  const candidate: number[] = [];

  const backtrack = (start: number) => {
    if (candidate.length === k) {
      result.push([...candidate]);
      return;
    }

    for (let i = start; i <= n; i++) {
      candidate.push(i); // 將數字 i 加入候選解
      backtrack(i + 1); // 遞迴呼叫下一個數字
      candidate.pop(); // 回溯：移除候選解的最後一個數字
    }
  };

  backtrack(1); // 從 1 開始遞迴
  return result;
}

> [name=Sheep][time=Tue, Aug 1, 2023]

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)