backtracking tips

refer this!

and my note

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]

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

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

Last updated 2 years ago