Problem#
給你兩個數字 $n$ 和 $k$ 問你能不能回傳從 $[1, n]$ 中挑 $k$ 個數字的所有組合
測資限制#
- $1 \le n \le 20$
- $1 \le k \le n$
想法#
窮舉 backtracking
兩個狀態：起始數字、目前挑到數字長度，搜索狀態從起始數字到數字$n$，當目前挑到數字長度大於 $k$ 時，代表搜索結束，輸出挑到的數字
- 時間複雜度: $\mathcal{O}(n!)$
- 空間複雜度: $\mathcal{O}(k)$
AC Code#
心得#
一開始 backtracking 寫成每次都會枚舉 $[1, n]$ ，但這樣會重複求出很多相同的組合 e.g. (1, 2), (2, 1) -> TLE