C++ easy DFS`s solution with explanation.


  • 2
    C
    void dfs(int step){
    
        ①判断边界;
    
        ②尝试每一种可能
        for (i = 1; i <= n; i++){
    
    	③继续下一步 dfs(step+1)
    
        }
        ④返回;
    }
    

    组合问题,深搜(回溯)枚举都可以用以上套路进行编码;

    以下就是此道题目对应的解决方法,每一个数用完回溯时记得把它捞回来重新用;

    class Solution {
    public:
        
        void dfs(int start, vector<int> &singlePer, vector<vector<int>> &result, 
                   vector<int> &nums, map<int, int> &book){
    
            if(start == nums.size()){
                result.push_back(singlePer);
                return;
            }
            
            for(int i = 0; i < nums.size(); i++){
                if(book[nums[i]] == 0){
                    singlePer[start] = nums[i];
                    book[nums[i]] = 1;
                    
                    dfs(start+1, singlePer, result, nums, book);
                    book[nums[i]] = 0;
                }
                
            }
            return;
        }
        
        vector<vector<int>> permute(vector<int>& nums) {
            
            vector<vector<int>> result;
            vector<int> singlePer(nums.size(), 0);
            
            map<int, int> book;
            for(int i = 0; i < nums.size(); i++)
                book[nums[i]] = 0;
            
            dfs(0, singlePer, result, nums, book);
            
            return result;
        }
    };

  • -8

    狂拽酷炫吊炸天!厉害的!!holy high! !!!!!!!!!!!!!!!!!!!!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.