引言40. 组合总和 II - 力扣LeetCode93. 复原 IP 地址 - 力扣LeetCode78. 子集 - 力扣LeetCode491. 非递减子序列 - 力扣LeetCode46. 全排列 - 力扣LeetCode47. 全排列 II - 力扣LeetCode51. N 皇后 - 力扣LeetCode代码第一题这个题目的最大难题就是去重所以我们先对于这个数组进行一个排序那么我们就可以从小到大一个一个的遍历只要当我们的和大于目标的时候我们就直接开始回溯。而且这样可以把相同的元素放在一起便于我们的去重。我们去重的方法用到了used数组只要这个元素和前面一个元素相同并且前面一个元素没有被使用过了那么就说明这两个元素已经重复。为什么是没有被使用过呢因为如果是使用过的说明这是第一次出现这个组合比如 {122}但是如果是没有使用过那么就说明我们是在回溯的过程之中那个数因为之前已经被处理过了所以被标记为了false。之所以我们不是直接用当前元素和上一个元素进行比较是因为我们是在回溯我们需要确定所有元素的情况而不是单一的一个相对为止i和i-1。class Solution { public: vectorint path; vectorvectorint res; void traversal(vectorint candidates, int target, int sum, int startIndex, vectorbool used) { if (sum target) { return; } if (sum target) { res.push_back(path); return; } for (int i startIndex; i candidates.size() sum candidates[i] target; i) { if (i 0 candidates[i] candidates[i - 1] used[i - 1] false) { continue; } used[i] true; sum candidates[i]; path.push_back(candidates[i]); traversal(candidates, target, sum, i 1, used); path.pop_back(); used[i] false; sum - candidates[i]; } } vectorvectorint combinationSum2(vectorint candidates, int target) { vectorbool used(candidates.size(), false); sort(candidates.begin(), candidates.end()); traversal(candidates, target, 0, 0, used); return res; } };第二题这一题考察的是分割字符串我们的startIndex不再是数组的字母了而是字母间的位置。我们每一次分割一段字串之后都会进行判断而我们的起点一个是startIndex终点是i这个点我们可以理解成每一个数组元素后面的那个空格比如i 0那么就对应的是第0个元素后面的那一个空格所以这也是一个左闭右闭得范围。然后我们每一次插入都要确定这个字串是符合规定得如果不符合规定那么就结束这个循环因为再往后遍历肯定也不符合。最后一定要注意我们插入得那个元素会改变整个数组得下标所以是i 2不再是i 1。class Solution { public: vectorstring res; bool isValid(const string s, int start, int end) { if (start end) { return false; } if (s[start] 0 start ! end) { return false; } int num 0; for (int i start; i end; i) { if (s[i] 9 || s[i] 0) { return false; } num num * 10 (s[i] - 0); if (num 255) { return false; } } return true; } void traversal(string s, int startIndex, int pointNum) { if (pointNum 3) { if (isValid(s, startIndex, s.size() - 1)) { res.push_back(s); } return; } for (int i startIndex; i s.size(); i) { if (isValid(s, startIndex, i)) { s.insert(s.begin() i 1, .); pointNum; traversal(s, i 2, pointNum); pointNum--; s.erase(s.begin() i 1); } else { break; } } } vectorstring restoreIpAddresses(string s) { if (s.size() 4 || s.size() 12) { return res; } traversal(s, 0, 0); return res; } };第三题这一题的主要难题就是怎么记录子集我们一般来说都是判断一个条件然后把结果放进去但是因为子集不需要任何判断的条件所以要放到最开始反而判断的作用仅仅是为了可以回溯。所以我们需要理解我们记录的意义到底是什么class Solution { public: vectorint path; vectorvectorint res; void traversal(vectorint nums, int startIndex) { res.push_back(path); if (path.size() nums.size()) { return; } for (int i startIndex; i nums.size(); i) { path.push_back(nums[i]); traversal(nums, i 1); path.pop_back(); } } vectorvectorint subsets(vectorint nums) { traversal(nums, 0); return res; } };第四题这一题的难点是我们需要对没有排序的数组进行去重所以我们不可以使用used数组了我们这里引用uset但是注意一下我们uset这个是在函数里面定义的也就是说每一层的递归都有一个新的uset。因为我们去重的目的就是每一层去重。我们这里深入了两个概念一个是层一个是树枝。层代表了这一个循环也就是取决于开始的位置也就是startIndex。可是为什么我们之前一直没有关心这个呢是因为我们之前一直都是处理树枝就是递归后的结果而这里需要的是一层一层的结果。class Solution { public: vectorint path; vectorvectorint res; void traversal(vectorint nums, int startIndex) { if (path.size() 1) { res.push_back(path); } unordered_setint uset; for (int i startIndex; i nums.size(); i) { if ((!path.empty() nums[i] path.back()) || uset.find(nums[i]) ! uset.end()) { continue; } uset.insert(nums[i]); path.push_back(nums[i]); traversal(nums, i 1); path.pop_back(); } } vectorvectorint findSubsequences(vectorint nums) { traversal(nums, 0); return res; } };第五题这是一个全排列的问题也就是说和起点没有什么关系所以我们这里和startIndex没啥关系但是因为要记录我们之前遍历了哪一些点所以我们用另外一个数组used来记录。class Solution { public: vectorint path; vectorvectorint res; void traversal(vectorint nums, vectorbool used) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (used[i] false) { used[i] true; path.push_back(nums[i]); traversal(nums, used); used[i] false; path.pop_back(); } else { continue; } } } vectorvectorint permute(vectorint nums) { vectorbool used(nums.size(), false); traversal(nums, used); return res; } };第六题这一题也是全排列而且还需要去重。所以我们必须要理解我们到底在哪里收集数据。我们肯定是在最后面也就是树枝的末尾接受数据但是因为是全排列所以我们还是不需要startIndex然后我们依然先排序把相同的数放在一起然后我们按照原来的去重逻辑不过还有一点要注意的是因为这个是全排列所以我们每一次都是从0开始遍历的所以不要忘记了在操作的时候要判断这个数是不是已经被记录了哦~~~class Solution { public: vectorint path; vectorvectorint res; void traversal(vectorint nums, vectorbool used) { if (path.size() nums.size()) { res.push_back(path); return; } for (int i 0; i nums.size(); i) { if (i 0 nums[i] nums[i - 1] used[i - 1] false) { continue; } if (used[i] false) { path.push_back(nums[i]); used[i] true; traversal(nums, used); path.pop_back(); used[i] false; } } } vectorvectorint permuteUnique(vectorint nums) { vectorbool used(nums.size(), false); sort(nums.begin(), nums.end()); traversal(nums, used); return res; } };第七题首先我们需要一个函数来判断我们这个点是不是符合规矩的。然后我们的落子路线是一行一行的所以我们不需要判断每一行是不是符合规矩的因为我们下棋的时候就已经保证了每一行只有一个。然后我们需要在每一行开始遍历每一列所以for。环是从0开始的但是我们路线是根据一行一行来的所以我们传递参数的时候需要记录一下当前是第几行的。这也就是N皇后的解法其实也不是很难一层一层的遍历。class Solution { public: vectorvectorstring res; bool isValid(int row, int col, vectorstring chessboard, int n) { for (int i 0; i row; i) { if (chessboard[i][col] Q) { return false; } } for (int i row - 1, j col - 1; i 0 j 0; i--, j--) { if (chessboard[i][j] Q) { return false; } } for (int i row - 1, j col 1; i 0 j n; i--, j) { if (chessboard[i][j] Q) { return false; } } return true; } void traversal(vectorstring chessboard, int row, int n) { if (row n) { res.push_back(chessboard); return; } for (int col 0; col n; col) { if (isValid(row, col, chessboard, n)) { chessboard[row][col] Q; traversal(chessboard, row 1, n); chessboard[row][col] .; } } } vectorvectorstring solveNQueens(int n) { std::vectorstd::string chessboard(n, std::string(n, .)); traversal(chessboard,0 , n); return res; } };
