My C++ solution, using backtracking, similar with what is used in solving N Queens problem


  • 0
    Z
    class Solution {
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            int n=nums.size();
            vector<vector<int>> res;
            if(n<1) return res;
            if(n==1){
                res.push_back(nums);
                return res;
            }
            vector<int> index(n,0);
            
            int i=1;
            int flag;
            while(index[0]<n){
                flag=1;
                for(int i0=0;i0<i;i0++){
                    if(index[i0]==index[i]){
                        flag=0;
                        index[i]++;
                        break;
                    }
                }
                
                if(flag){
                    if(i==n-1){
                        vector<int> temp;
                        for(int j=0;j<n;j++)
                        temp.push_back(nums[index[j]]);
                        res.push_back(temp);
                        i--;
                        index[i]++;
                    }
                    else{
                        i++;
                        index[i]=0;
                    }
                }
                
                while(index[i]==n && i>0){
                    i--;
                    index[i]++;
                }
            }
            return res;
        }
    };
    

    Besides, if modifying only one sentence, i.e, modifying "if(index[i0]==index[i] )" to "if(index[i0]==index[i] || (nums[index[i0]]==nums[index[i]] && index[i0]>index[i]))", we can solve Permutations II directly.


Log in to reply
 

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