My elegant recursive C++ solution with inline explanation


  • 187
    X

    This recursive solution is the my first response for this problem. I was surprised when I found no similar solution posted here. It is much easier to understand than DFS-based ones, at least in my opinion. Please find more explanations here. All comments are welcome.

    class Solution {
    public:
        vector<vector<int> > permute(vector<int> &num) {
    	    vector<vector<int> > result;
    	    
    	    permuteRecursive(num, 0, result);
    	    return result;
        }
        
        // permute num[begin..end]
        // invariant: num[0..begin-1] have been fixed/permuted
    	void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
    		if (begin >= num.size()) {
    		    // one permutation instance
    		    result.push_back(num);
    		    return;
    		}
    		
    		for (int i = begin; i < num.size(); i++) {
    		    swap(num[begin], num[i]);
    		    permuteRecursive(num, begin + 1, result);
    		    // reset
    		    swap(num[begin], num[i]);
    		}
        }
    };
    

  • 22
    H

    well, that's just what I've done:

        void dfs(int pos, vector<int> &num, vector<vector<int>> &result){
        if(pos == num.size()){
            result.push_back(num);
        }
        else{
            for(int i=pos; i<num.size(); i++){
                swap(num[i], num[pos]);
                dfs(pos+1, num, result);
                swap(num[i], num[pos]);
            }
        }
    

  • 2
    T

    Really smart. Even though my idea is exactly same with yours, I used some extra space to keep the num and current permutation. Yours is much better since no extra space has been used.


  • 0
    T

    I modified your code for permutation II, but something wrong happened. Will you plz take a look at my post: https://oj.leetcode.com/discuss/19826/adding-two-lines-to-permutation-why-got-output-limit-exceed


  • 1
    A

    love the swap idea, avoid maintaining record of which indices have been visited using an extra set or list. def make code slimmer.


  • 1
    T

    How about
    if (begin >= num.size()) to if (begin >= num.size()-1) will better.


  • 0
    X

    Brilliant...


  • -1
    X

    btw this assumes that there are no duplicates right? Otherwise there will be duplicates in the output?


  • 0
    X

    Right. It's not difficult to modify it to handle duplicates as https://oj.leetcode.com/discuss/20879/sharing-short-solution-using-dfs-modified-from-permutation does.


  • 0
    X

    Here is the modification to cope with duplicates http://xiaohuiliucuriosity.blogspot.com/2015/03/permutations-ii.html


  • 3

    You may change the reference vector<int>& to vector<int> in permuteRecursive() and then you won't need the second swap statements. However, your way is more space-efficient.


  • 6
    D

    Thanks for smart code. Following is the Java version.

    public class Solution {
    public List<List<Integer>> permute(int[] num) {
     List<List<Integer>> result = new ArrayList<List<Integer>>(); 
     permute(num,0,result);
     return result;}
    
    
     public void permute(int[] num, int begin, List<List<Integer>> result){
        if(begin>=num.length){
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0;i<num.length;i++){
                list.add(num[i]);
            }
            result.add(list);
            return;
        }
        for(int i=begin;i<num.length;i++){
            swap(begin,i,num);
            permute(num,begin+1,result);
            swap(begin,i,num);
            
        }
    }
    
    public void swap (int x, int y,int[] num){
        int temp = num[x];
        num[x]=num[y];
        num[y]=temp;
    } }

  • 1
    R

    can you please analyse space and time complexity? thanks


  • 1
    D

    It's hard to understand the process of recursive.


  • 0
    T

    Hi,

    In the permuteRecursive( ), for nums, is the reference & necessary? I think it is ok to not pass by reference. Passing by reference can only save space, right?


  • 0
    S

    I think passing by reference also saves time because the vector on the receiving end doesn't need to copy the whole vector values. CMIIW.


  • 1
    S

    What's the time complexity of this?


  • 1
    A

    Please laugh at my answer, I think the nums maybe include repeat int,so do a repeat check

    vector<vector<int>> permute(vector<int>& nums)
    {
        vector<vector<int>> vvOutput;
        int iLength = nums.size();
        vector<int> vTemp(iLength, 1);
        ProductPermute(0, nums, vTemp, vvOutput);
        return vvOutput;
    }
    void	ProductPermute(int iNumIndex, vector<int> nums, vector<int> vTemp, vector<vector<int>> &vvOutput)
    {
        int iLength = nums.size();
        if(0 == iLength)
        {
            vvOutput.push_back(vTemp);
            return;
        }
        for(int iIndex = 0; iIndex < iLength; iIndex++)
        {
            if(CheckPermuteRepeat(iNumIndex, nums[iIndex], vTemp, vvOutput))
            {
                vTemp[iNumIndex] = nums[iIndex];
                vector<int> vCopy = nums;
                vCopy.erase(vCopy.begin() + iIndex);
                ProductPermute(iNumIndex + 1, vCopy, vTemp, vvOutput);
            }
        }
    }
    int CheckPermuteRepeat(int iNumIndex, int iValue, vector<int> vTemp, vector<vector<int>> vvOutput)
    {
        int iLine = vvOutput.size();
        vTemp[iNumIndex] = iValue;
        for(int iIndexLine = 0; iIndexLine < iLine; iIndexLine++)
        {
            int iIndexRow = 0;
            for(; iIndexRow <= iNumIndex; iIndexRow++)
            {
                if(vvOutput[iIndexLine][iIndexRow] != vTemp[iIndexRow])
                    break;
            }
            if(iIndexRow == iNumIndex+1)
                return 0;
        }
        return 1;
    }

  • 3
    S

    this is basically the same as DFS


  • 2
    R

    if (begin >= num.size())
    The "IF" condition can be if (begin >= num.size()-1) because even at the last index, there are no more changes made.


Log in to reply
 

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