Leetcode101

定义flag 标记元素是否已访问

class Solution {
public:
    vector path;
    void backtrack(vector &nums, vector> &ans,vector& flag){
        if(path.size() == nums.size()){
            ans.push_back(path);
            return;
        }
        for(int k = 0; k < nums.size(); k++){
            if(flag[k] == 0){
                path.push_back(nums[k]);
                flag[k] = 1;
                backtrack(nums,ans,flag);
                flag[k] = 0;
                path.pop_back();
            }
        }
    }
    vector> permute(vector& nums) {
        vector> ans;
        vector flag(nums.size(),0);
        backtrack(nums,ans,flag);
        return ans;
    }
};

类似于排列问题，我们也可以进行回溯。排列回溯的是交换的位置，而组合回溯的是是否把当前的数字加入结果中。

class Solution {
public:
    vector path;
    void back(int n, int k,int pos,int count, vector>& ans){
        if(count == k){
            ans.push_back(path);
            return;
        }
        for(int i = pos; i <= n; i++){
            count++;
            path.push_back(i);
            back(n,k,i + 1,count,ans);
            count--;
            path.pop_back();
        }
    }
    vector> combine(int n, int k) {
        vector> ans;
        int count = 0;
        back(n,k,1,count,ans);
        return ans;
    }
};

class Solution {
public:
    vector> ans;
    void dfs(vector& candidates, int target,vector& now,int index){
        if(target < 0 || index >= candidates.size()) return;
        if(target == 0){
            ans.push_back(now);
            return;
        }
        now.push_back(candidates[index]);
        dfs(candidates,target - candidates[index],now,index);
        now.pop_back();
        dfs(candidates,target,now,index + 1);
    }
    vector> combinationSum(vector& candidates, int target) {
        vector now;
        dfs(candidates,target,now,0);
        return ans;
    }
};

深度优先搜索 回溯

class Solution {
public:
    vector direction = {-1,0,1,0,-1};
    void dfs(bool& find,vector>& board, string& word,vector>& flag,int x,int y,int size,int index){
        if(!(x >= 0 && x < board.size() && y >= 0 && y < board[0].size())) return;
        if(flag[x][y] == 1 || board[x][y] != word[index]) return;
        if(index == size - 1){
            find = true;
            return;
        }
        flag[x][y] = 1;
        for(int k = 0; k < 4; k++){
            int p = x + direction[k];
            int q = y + direction[k + 1];
            dfs(find,board,word,flag,p,q,size,index + 1);
        }
        flag[x][y] = 0;
    } 
    bool exist(vector>& board, string word) {
        int m = board.size();
        int n = board[0].size();
        int size = word.size();
        int index = 0;
        bool find = false;
        vector> flag(m,vector (n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                 dfs(find,board,word,flag,i,j,size,index);
            }
        }      
        return find;
    }
};