1 class Solution { 2 public: 3     void dfs(int dep, int maxDep, vector<int>& cand, int target) 4 { 5     if (target < 0)return; 6     if (dep == maxDep) 7     { 8         if (target == 0)//到达尾部且等于target 9         {10               vector<int> temp;11               for (int i = 0; i < maxDep; i++)12               {13                 for (int j = 0; j < num[i]; j++)14                     temp.push_back(cand[i]);15               }16                 ret.push_back(temp);17             }18             return;19         }20         for (int i = 0; i <= target / cand[dep]; i++)//枚举合适的情况21         {22             num[dep] = i;23             dfs(dep + 1, maxDep, cand, target - i*cand[dep]);24         }25 }26 vector<vector<int>> combinationSum(vector<int>& candidates, int target) 27 {28     int n = candidates.size();29     if (n == 0)return ret;30     sort(candidates.begin(), candidates.end());31     num.resize(n);32     ret.clear();33     dfs(0, n, candidates, target);34     return ret;35 36 }37 private:38     vector<vector<int>> ret;//返回的结果39     vector<int> num;//用来存储每个数字的次数40 };

 1 class Solution { 2 public: 3 void dfs(int dep, int maxDep, vector<int>& cand, int target) 4 { 5     if (target < 0)return; 6     if (dep == maxDep) 7     { 8         if (target == 0) 9         {10               vector<int> temp;11               for (int i = 0; i < maxDep; i++)12               {13                 for (int j = 0; j < num[i]; j++)14                     temp.push_back(cand[i]);15               }16                 res.insert(temp);17             }18             return;19         }20         for (int i = 0; i<=1; i++)21         {22             num[dep] = i;23             dfs(dep + 1, maxDep, cand, target - i*cand[dep]);24         }25 }26 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) 27 {28     int n = candidates.size();29     if (n == 0)return ret;30     sort(candidates.begin(), candidates.end());31     num.resize(n);32     ret.clear();33     dfs(0, n, candidates, target);34     set<vector<int>>::iterator it= res.begin();35     for (;it!=res.end();it++)36     {37         ret.push_back(*it);38     }39     return ret;40 41 }42 43 private:44     vector<vector<int>> ret;45     set<vector<int>> res;46     vector<int> num;47 };

 1 class Solution { 2 public: 3     void dfs(int pos, string &str, int left, int remain, int n){   // left表示左边有多少个左括号没有关闭 4         if(remain == 0){  // 左括号使用完毕  故全部为右括号 5             for(int i = pos; i < 2*n; i++) 6                 str[i] = ‘)‘; 7             result.push_back(str); 8             return; 9         }10         11         if(remain > 0){             // remain!=0 说明还可以使用左括号12             str[pos] = ‘(‘;13             dfs(pos+1, str, left+1, remain-1, n);14         }15         if(left != 0){               // left！=0 表示左边还有左括号没有关闭，故可以使用)16             str[pos] = ‘)‘;17             dfs(pos+1, str, left-1, remain, n);18         }19     }20     vector<string> generateParenthesis(int n) {21         string str;22         str.resize(2*n);23         dfs(0, str, 0, n, n);24         return result;25         26     }27 private:28     vector<string> result;29 };

 1 class Solution { 2 private: 3     vector<vector<int>> result; 4     vector<int> tmp; 5 public: 6     void dfs(int dep, const int &n, int k, int count) 7     { 8         if (count == k) 9         {10             result.push_back(tmp);11             return;12         }13         if (dep < n - k + count)14         {15             dfs(dep + 1, n, k, count);//不取当前数16         }17         tmp[count] = dep + 1;         //取当前数18         dfs(dep + 1, n, k, count+1);19         20     }21     vector<vector<int>> combine(int n, int k)22     {23         if (k>n)k = n;24         tmp.resize(k);25         dfs(0, n, k, 0);26         return result;27     }28 29 };

 1 string NumToStr[10] = {"", "","abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};  2 class Solution { 3 private: 4     string str; 5     vector<string> result; 6 public: 7     int charToInt(char c) 8     { 9         int i;10         stringstream ss;11         ss << c;12         ss >> i;13         return i;14     }15     void dfs(int dep, int maxDep, const string &digits)16     {17         if (dep == maxDep)18         {19             result.push_back(str);20         }21         int index = charToInt(digits[dep]);22         for (int i = 0; i < NumToStr[index].size(); i++)23         {24             str[dep] = NumToStr[index][i];25             dfs(dep+1,maxDep,digits);26         }27     }28 29     vector<string> letterCombinations(string digits)30     {31         int n = digits.size();32         if (n == 0)return result;33         str.resize(n);34         dfs(0,n,digits);35         return result;36     }37 };

 1 class Solution { 2 vector<int> hour = { 1, 2, 4, 8 }, minute = {1,2,4,8,16,32}; 3 public: 4     void helper(vector<string> & res, pair<int, int> time, int num, int start_point) 5     { 6         if (num == 0) 7         { 8             if (time.second < 10) 9                 res.push_back(to_string(time.first) + ":0" + to_string(time.second));10             else11                 res.push_back(to_string(time.first) + ":" + to_string(time.second));12             return;13         }14         for (int i = start_point; i < hour.size() + minute.size(); i++)15         {16             if (i < hour.size())17             {18                 time.first += hour[i];19                 if (time.first < 12)20                     helper(res, time, num - 1, i + 1);21                 time.first -= hour[i];22             }23             else24             {25                 time.second += minute[i - hour.size()];26                 if (time.second < 60)27                     helper(res,time,num-1,i+1);28                 time.second -= minute[i - hour.size()];29             }30         }31     }32     vector<string> readBinaryWatch(int num)33     {34         vector<string> res;35         helper(res,make_pair(0,0),num,0);36         return res;37     }38     39 };

 1 class Solution { 2 public: 3     vector<int>ans; 4     vector<vector<int>> res; 5     vector<vector<int>> subsets(vector<int>& nums) { 6         if(nums.empty())return res; 7         sort(nums.begin(),nums.end()); 8         dfs(0,ans,nums); 9         return res;10     }11     void dfs(int k,vector<int> ans, vector<int> nums)12     {13         res.push_back(ans);14         for(int i=k;i<nums.size();i++)15         {16             ans.push_back(nums[i]);17             dfs(i+1,ans,nums);18             ans.pop_back();19         }20     }21 };

 1 class Solution { 2 private: 3     vector<vector<string> > res; 4 public: 5     vector<vector<string> > solveNQueens(int n) { 6         vector<string>cur(n, string(n,‘.‘)); 7         helper(cur, 0); 8         return res; 9     }10     void helper(vector<string> &cur, int row)11     {12         if(row == cur.size())13         {14             res.push_back(cur);15             return;16         }17         for(int col = 0; col < cur.size(); col++)18             if(isValid(cur, row, col))19             {20                 cur[row][col] = ‘Q‘;21                 helper(cur, row+1);22                 cur[row][col] = ‘.‘;23             }24     }25      26     //判断在cur[row][col]位置放一个皇后，是否是合法的状态27     //已经保证了每行一个皇后，只需要判断列是否合法以及对角线是否合法。28     bool isValid(vector<string> &cur, int row, int col)29     {30         //列31         for(int i = 0; i < row; i++)32             if(cur[i][col] == ‘Q‘)return false;33         //右对角线(只需要判断对角线上半部分，因为后面的行还没有开始放置)34         for(int i = row-1, j=col-1; i >= 0 && j >= 0; i--,j--)35             if(cur[i][j] == ‘Q‘)return false;36         //左对角线(只需要判断对角线上半部分，因为后面的行还没有开始放置)37         for(int i = row-1, j=col+1; i >= 0 && j < cur.size(); i--,j++)38             if(cur[i][j] == ‘Q‘)return false;39         return true;40     }41 };

 1 class Solution { 2 private: 3     vector<vector<int>> result; 4     vector<int> visited; 5 public: 6     void dfs(int st, int n, vector<int>& v, vector<int>& nums) 7     { 8         if (st == n) 9         {10             result.push_back(v);11             return;12         }13         for (int i = 0; i < n; i++)14         {15             if (visited[i] != 1)16             {17                 visited[i] = 1;18                 v.push_back(nums[i]);19                 dfs(st + 1, n,v,nums);20                 v.pop_back();21                 visited[i] = 0;22             }23         }24     }25     vector<vector<int>> permute(vector<int>& nums)26     {27         int num = nums.size();28         visited.resize(num);29         vector<int> tmp;30         dfs(0,num,tmp,nums);31         return result;32     }33 34 };

 1 class Solution { 2 private: 3     vector<vector<int>> result; 4     vector<int> tmpResult; 5     vector<int> count; 6 public: 7     void dfs(int dep, int maxDep, vector<int>& num, vector<int> visited) 8     { 9         if (dep == maxDep)10         {11             result.push_back(tmpResult);12             return;13         }14         for (int i = 0; i < num.size(); i++)15         {16             if (i == 0)count[dep] = 0;17             if (!visited[i])18             {19                 count[dep]++;20                 if (count[dep]>1 && tmpResult[dep] == num[i])continue; 21                 // 每个位置第二次选数时和第一次一样则continue22                 visited[i] = 1;             // 每个位置第二次选择的数时和第一次不一样  23                 tmpResult[dep] = num[i];24                 dfs(dep + 1, maxDep, num, visited);25                 visited[i] = 0;26             }27         }28     }29     vector<vector<int>> permuteUnique(vector<int> &num)30     {31         sort(num.begin(), num.end());32         tmpResult.resize(num.size());33         count.resize(num.size());34         vector<int> visited;35         visited.resize(num.size());36         dfs(0, num.size(), num, visited);37         return result;38     }39 };

 1 class Solution { 2 public: 3     bool dfs(int xi, int yi, string &word, int index, vector<vector<char> > &board, const int &m, const int &n, int **visited){ 4         visited[xi][yi] = 1;        // 该结点已经访问过了 5         if(index + 1 < word.size()){ 6             if(xi-1 >= 0 && visited[xi-1][yi]==0 && board[xi-1][yi] == word[index+1]){ 7                 if(dfs(xi-1, yi, word, index+1, board, m, n, visited))return true;   //深度遍历 8                 visited[xi-1][yi] = 0;      // 这条路行不通 设为未访问 以不影响下面的遍历 9             }10             if(xi+1 <m && visited[xi+1][yi]==0 && board[xi+1][yi] == word[index+1]){11                 if(dfs(xi+1, yi, word, index+1, board, m, n, visited))return true;12                 visited[xi+1][yi] = 0;13             }14             if(yi-1 >= 0 && visited[xi][yi-1]==0 && board[xi][yi-1] == word[index+1]){15                 if(dfs(xi, yi-1, word, index+1, board, m, n,visited)) return true;16                 visited[xi][yi-1] = 0;17             }18             if(yi+1 < n && visited[xi][yi+1]==0 && board[xi][yi+1] == word[index+1]){19                 if(dfs(xi, yi+1, word, index+1, board, m, n,visited)) return true;20                 visited[xi][yi+1] = 0;21             }22             return false;23         }else return true;24     }25     26     void initVisited(int ** visited, const int &m, const int &n){27         for(int i = 0; i < m; i++)28             memset(visited[i], 0, sizeof(int)*n);29     }30     bool exist(vector<vector<char> > &board, string word) {31         int m = board.size();32         int n = board[0].size();33         int **visited = new int*[m];34         for(int i = 0; i < m; i++)35             visited[i] = new int[n];36         37         for(int i = 0; i < m; i++){   // 找到其中的i和j38             for(int j = 0; j < n; j++){39                 if(word[0] == board[i][j]){40                     initVisited(visited, m, n);41                     if(dfs(i, j, word, 0, board, m, n,visited)) return true;42                 }43             }44         }45         for(int i = 0; i < m; i++)46             delete []visited[i];47         delete []visited;48         return false;49     }50 };