C++ DFS

子集

78. 子集

法一：思路对每个元素进行选与不选的选择，这样正好到最后一层就是2的size()次方个，叶子就是节点，通过pos来控制深度

法二：通过for循环实现，且下一个栈帧的i是上一个栈帧当前元素的下一个位置，能起到vis的作用刚开始写的时候把这个->dfs(nums, i + 1); 写成了dfs(nums, pos + 1);

解释为什么dfs(nums, pos + 1);是错的且当样例为[1,2,3]时有16个结果

其实就是逻辑上不对，每一个for循环进到下一个栈帧的区间都是一样的，这就是问题所在；

总结：在for里i=pos上，有一点点语法的混淆，加上脑子不清醒，逻辑不清晰，梳理好了在写，不然还得重新检查

法一：

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()) {ret.push_back(path); return;}path.push_back(nums[pos]);dfs(nums, pos + 1);path.pop_back();dfs(nums,pos + 1);}
};

法二：

class Solution {
public:vector<int> path;vector<vector<int>> ret;vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){ret.push_back(path);for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);dfs(nums, i + 1);path.pop_back();}}
};

全排列

46. 全排列

通过pos来控制栈帧深度，pos+1来增加深度，pos也是用来取值的

在代码上表现逻辑：当需要dfs往下走的时候，需要对已经当前元素改bool值，来保证到下一层不被使用；当dfs回来之后自然的要把当前元素弹出path（其实每个栈的深度，就是这个元素在path里的位置）我们只需要弹出它，让他去后面的其他位置，同时需要解锁bool值

题外话：保持其他代码不变，删掉弹出语句，最大长度是多少？

答：15个，第一个栈帧可以发送3个值，同时需要三个栈帧（注意：在此时深度仍然是2），这三个栈帧每个可以向下个栈帧发送2个值，会有6个栈帧；这6个栈帧每个可以发送一个值，那就是2+3*2+6=15，一共会创建16个栈帧（因为到进不去for那个栈帧才结束），最大深度为4

class Solution {
public:vector<vector<int>> ret;vector<int> path;vector<bool> vis;//bool[6];vector<vector<int>> permute(vector<int>& nums) {vis.resize(nums.size());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(vis[i] == true) continue;path.push_back(nums[i]);vis[i] = true;dfs(nums, pos + 1);path.pop_back();vis[i] = false;}}
};

找出所有子集的异或总和再求和

1863. 找出所有子集的异或总和再求和

class Solution {
public:int ret = 0;int subsetXORSum(vector<int>& nums) {dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){ret += sum;for(int i = pos; i < nums.size(); i++){sum = sum ^ nums[i];dfs(nums, i + 1, sum);sum ^= nums[i];}}
};

全排列 II

47. 全排列 II

1. 去重想到的就是set，set里放vector<int>

2. 剪枝

class Solution {
public:set<vector<int>> set;vector<bool> vis;vector<int> path;vector<vector<int>> permuteUnique(vector<int>& nums) {vis.resize(nums.size());dfs(nums, 0);vector<vector<int>> ret(set.begin(), set.end());return ret;}void dfs(vector<int>& nums, int pos){if(path.size() == nums.size()){set.insert(path);}for(int i = 0; i < nums.size(); i++){if(vis[i]) continue;path.push_back(nums[i]);vis[i] = true;dfs(nums, pos + 1);vis[i] = false;path.pop_back();}}
};

class Solution {
public:vector<bool> vis;vector<int> path;vector<vector<int>> ret;vector<vector<int>> permuteUnique(vector<int>& nums) {vis.resize(nums.size());sort(nums.begin(), nums.end());dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if(pos == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); i++){if(vis[i] == true || i != 0 && nums[i] == nums[i - 1] && vis[i - 1] == false) continue;path.push_back(nums[i]);vis[i] = true;dfs(nums, pos + 1);path.pop_back();vis[i] = false;}}
};

电话号码的字母组合

17. 电话号码的字母组合

代码问题：arr[digits[pos] - '0'];忘记是字符了

逻辑问题：digiis可能是空串，空串进入dfs就会被压入 "" 空字符串

class Solution {
public:vector<string> arr{ "","","abc","def" ,"ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> ret;string path;vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits, 0);return ret;}void dfs(string digits, int pos){if (pos == digits.size()){ret.push_back(path);return;}string tmp = arr[digits[pos] - '0'];for (auto e : tmp){path.push_back(e);dfs(digits, pos + 1);path.pop_back();}}
};

组合

77. 组合

class Solution {
public:vector<int> path;vector<bool> vis;vector<vector<int>> ret;int _k;vector<vector<int>> combine(int n, int k) {_k = k;vector<int> arr(n);for (int i = 0; i < n; i++)arr[i] = i + 1;dfs(arr, 0);return ret;}void dfs(vector<int>& arr, int pos){if (path.size() == _k){ret.push_back(path);return;}for (int i = pos; i < arr.size(); i++){path.push_back(arr[i]);dfs(arr, i + 1);path.pop_back();}}
};

class Solution {
public:vector<int> path;vector<vector<int>> ret;int _k, _n;vector<vector<int>> combine(int n, int k) {_k = k;_n = n;dfs(0);return ret;}void dfs(int pos){if (path.size() == _k){ret.push_back(path);return;}for (int i = pos; i < _n; i++){path.push_back(i + 1);dfs(i + 1);path.pop_back();}}
};

目标和

494. 目标和

发现局部sum不需要sum += nums[pos];这样的加回去的操作，因为每一个栈帧里的sum都是不一样的，而全局sum会一直改变，一个栈帧里的操作不能影响同层栈帧

全局sum

class Solution {
public:int sum = 0, ret = 0,_target;int findTargetSumWays(vector<int>& nums, int target) {_target = target;dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){if (pos == nums.size()){if (_target == sum)ret++;return;}sum += nums[pos];dfs(nums, pos + 1);sum -= nums[pos];sum -= nums[pos];dfs(nums, pos + 1);sum += nums[pos];}
};

局部sum

class Solution {
public:int ret = 0,_target;int findTargetSumWays(vector<int>& nums, int target) {_target = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){if (pos == nums.size()){if (_target == sum)ret++;return;}sum += nums[pos];dfs(nums, pos + 1, sum);sum -= nums[pos];sum -= nums[pos];dfs(nums, pos + 1, sum);}
};

组合总和

39. 组合总和

参开代码

class Solution {
public:vector<int> path;int _target;vector<vector<int>> ret;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {_target = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){if(sum == _target){ret.push_back(path);return;}if(sum > _target || pos == nums.size()) return;for(int i = 0; i * nums[pos] + sum <= _target; i++){if(i) path.push_back(nums[pos]);dfs(nums, pos + 1, i * nums[pos] + sum);// while(i--)//     path.pop_back();    //不对必须是整个for结束，不然i走不下去了}for(int i = 1; i * nums[pos] + sum <= _target; i++) path.pop_back();}
};

超时：

class Solution {
public://vector<vector<int>> ret;int _target, sum = 0;vector<int> path;set<vector<int>> set;vector<vector<int>> combinationSum(vector<int>& candidates, int target) {vector<int> nums;for (auto e : candidates){int n = target / e;for (int i = 0; i < n; i++)nums.push_back(e);}_target = target;dfs(nums, 0);vector<vector<int>> ret(set.begin(), set.end());return ret;}void dfs(vector<int>& nums, int pos){if(sum == _target)set.insert(path);if (pos == nums.size()) return;for (int i = pos; i < nums.size(); i++){path.push_back(nums[i]);sum += nums[i];dfs(nums, i + 1);sum -= nums[i];path.pop_back();}}
};

括号生成

22. 括号生成

条件约束递归

class Solution {
public:string path;vector<string> ret;int _n, left = 0, right = 0;vector<string> generateParenthesis(int n) {_n = n;dfs();return ret;}void dfs(){if(right == _n) {ret.push_back(path);return;}if (left < _n){path.push_back('(');left++, dfs();path.pop_back(); left--;}if (right < left){path.push_back(')');right++, dfs();path.pop_back(); right--;}}};

判断是不是平衡二叉树

判断是不是平衡二叉树_牛客题霸_牛客网

dfs的返回值：-1为false 非0为高度差，这个想法很6★★★★

left和right是不用+1的，因为这个1是root这个位置

class Solution {
public:bool IsBalanced_Solution(TreeNode* pRoot) {return dfs(pRoot) != -1;}int dfs(TreeNode* root){if (root == nullptr) return 0;int left = dfs(root->left);if (left == -1) return -1;int right = dfs(root->right);if (right == -1) return -1;return abs(left - right) <= 1 ? max(left, right) + 1: -1;}
};