> For the complete documentation index, see [llms.txt](https://timmybeeflin.gitbook.io/cracking-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/dfs/tips.md).

# 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>

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC2MQwPWlbviLhOpVw%2F-MiC7QCXXNwTfkaF_a4R%2Fimage.png?alt=media\&token=efb688d6-e74b-416c-9559-42ee178f839a)

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]**

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MiC7zjixr-5KBBiGHyc%2F-MiC9bRVa4kNetaWnuMg%2Fimage.png?alt=media\&token=411f0af4-21b0-42ed-8392-d17b97a72b65)

### 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