[LeetCode] 77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]
題目簡單明瞭, 我們要找出所有的組合 以上面的範例來說就是 在1,2,3,4 中取兩個數字組成一個組合. 這裡要注意的是 [1,3] 和 [3,1] 算是同一個組合.所以不能重複計算.

我們用DFS來解,

line 5: 有個testcase: 20取 16 會超時. 這裡我們可以早點停止尋找  如果剩下的可選數字 不能填滿組合 就剪枝(backtracking). remaining elements is smaller than needed to fill combination

line 7: path 裡的數字滿足 k. 用deep copy 複製一個新的list 然後加到res去

line 10 -12 : dfs

 

留言