backtracking tips

refer this!

https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247490981&idx=1&sn=db17864d2f6f189d63e051e434c05460&scene=21#wechat_redirect

and my note

https://wool-lamprey-b10.notion.site/Backtracking-0e4f2415e1f24bbf9745c78c14600ab0

permutation: use used[], ex: 46,47

combination: use start, ex: 39, 77, 78

backtracking, we always have a tree (ex: [2, 3, 6, 7]), then cut and find the ans.

[2, 3, 6, 7]

permutation (排列, 有序

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

combination 組合, 忽略順序

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

combination 就是找元素來奏合, 所以湊合的過程, 不希望之前用過的再被用過, 所以會用 i = start

記住這個 idea... (subset) , subset 和 combination idea 都一樣, 都用 i = start 來使下一層不選到使用過的元素

[]

/ 1

[1,2] [1, 3]

permutation 則不一樣, 因為要列出所有個數一樣的排列, 所以用 used[]

combination 和 subset 並不需要所有結果個數是一樣, 所以用 i = start