Easy to understand C++ recursive solution (explanation)


  • 0
    L

    Summary in short: DFS, backtracing, hash table

    Main idea:
    Use a set (the data structure named table in the code) to track the available numbers. During the DFS, each number can be used once in each path, so we need to track which numbers are not yet used. Each step, we grab an available number from the set, and call recursive function for this number. Inside recursive call, we construct a partial result by adding one number into it in each step. When we reach the leaf node, we have a complete combination to be added to the final result vector.

    When we trace back to the upper lever, we remove one number from the partial result, and put that number back into the candidate set. And go into another branch of recursion function call with another number. Then continue the above process.

    We continue this process and go through all the possible branches of the tree. And every time when we reach a leaf node, which is one of the possible combination, we should add the corresponding partial result into the final vector.

    After we finish all the recursion function callings, we go back to the top level of the tree. At this time, we have already got all the possible combinations in the final result vector. Done!

    Example:
    *Assume we have [1, 2, 3]
    *Assume we have a recursive function called help(int i) to search the sub tree with node i;
    steps
    1, initially, the set is initialized to {1, 2, 3}
    2, We call help() for each value in the set: help(1), help(2) and help(3)
    3, In help(1), we first remove 1 from the set, now we have {2, 3} in the set. And we push number 1 into a partial result vec (vec={1}).
    4, Now, we need to go further to search the sub-branches, we use a loop to go through 2 and 3. We call help(2) and help(3)

    1. In help(2), we remove 2 from the set, the candidate set becomes {3}. And we push number 2 into a partial result ((vec={1, 2}).Then we call help(3).
    2. In help(3), we remove 3 from the set. Now the set is empty. And we push number 3 into a partial result (vec={1, 2, 3}). We notice that we have arrived at a leaf node, vec is a combination we want. We push this combination into the final result array. And it is the time to return to the upper level. Before returning from help(3), we pop up the last element (3) in vec (using vec.pop_back()), vec becomes {1, 2}. And add 3 back into the candidate set ({3}). Then we return from help(3).
    3. In the upper level, we need to return from help(2). Before that, we pop the last element of vec, vec becomes {1}, and we add 2 back to the candidate set (set becomes {2, 3}). Then we return from help(2)
    4. Since we returned from help(2). We will call recursive function help(3), go to another branch. Following the steps above, we can get another combination {1, 3, 2}.
    5. At this time, we have finished help(1). We pop the last element (1) of vec, vec becomes empty. We also put 1 back into candidate set, the set becomes {1, 2, 3}. Then we return from help(1)
    6. After finishing help(1). We dive into help(2). We can get {2, 1, 3} and {2, 3, 1}
    7. Then we dive into help(3). after a series recursion, we can get {3, 1, 2} and {3, 2, 1}.
    8. Then we finished all the steps. We get our final result in the vector.

    The following is the code.

    class Solution {
    public:
        vector<vector<int>> result;  // Final result
        vector<int> vec; // Partial result for each path
        unordered_map<int, bool> table; // Hash table to track the available set
        int table_size; // track the count of available numbers in the above set.
    
        void help(int i){  // Recursive help function.
            vec.push_back(i);
            if(table_size == 1){ // If we have reached leaf node, we need to push the partial result to the final result.
                result.push_back(vec);
                vec.pop_back();
                return;
            }
            table[i] = false; // Remove current number from the set (we do not really remove it from the hash table, just mark it as false)
            table_size --;
    
            for (auto & node : table) // For every available candidate number in the set, call recursive function.
                if(node.second == true) help(node.first);
            
            vec.pop_back(); // remove the last element from the partial result
            table[i] = true; // "add" the number back to the candidate set
            table_size ++;
        }
        
        vector<vector<int>> permute(vector<int>& nums) {
            int n = nums.size();
            if(n == 0) return result;
            
            table_size = 0; // Construct the candidate set.
            for(auto & i : nums) {
                table[i] = true;
                table_size ++;
            }
            for(auto & i : nums) help(i); // Start the DFS search.
                
            return result;
        }
    };
    

Log in to reply
 

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