LeetCode｜backtracking｜review：40. 131. 93. 47. 332. | 37. Sudoku Solver

复习：

40. Combination Sum II

[1,1,2,3]中，答案里有[1,1,2], 但是不能有两个[1,2,3]

131. Palindrome Partitioning

每个for都是在给定的start之后找一个palindrome。当start

93. Restore IP Addresses

forloop每次loop都是在给定的start的后三个数字中找可以打点的地方

s.insert(s.begin() + i + 1 , '.'); s.erase(s.begin() + i + 1);

47. Permutations II

【1，1，2，3】

两种记录：

1. 看在本层内某个数字是不是已经被用过了。

已经有1，1，2，3了不需要第二个1，1，2，3。这种都是call self之前标为true，callself后标为false

2. 看到下一层后某个元素是不是已经被用过了。仅限permutation。（因为combination和子集问题i从start开始，permutation的i从0开始）（包括有序sequence，也是需要按照顺序 i = start一点一点往后看的）

已经有1，1，2了，进到第四层，不再去看2了。

332. Reconstruct Itinerary

 这种traverse map的方法比较合适。

选map因为需要计数且需要排序。

 

37. Sudoku Solver

抓重点：backtrack在那个forloop里被call。也就是说，backtracking试错的动作怎么试。这道题是试填1还是23456...

return false的地方：某一个方案一直往下填充，到后面发现没有符合条件的数字了，就只能return false，在上一层试另一种选择