Leetcode 46. Permutations

Permutations

Permutations :

給定一組陣列,回傳該陣列的所有的排列可能。

Python

遞歸求解:

如果nums的長度小於等於1,回傳nums

用python enumerate函式來求解,先選出來一個出來[1],剩下[2,3],再繼續做遞歸,最後把先選出來的1,跟剩下兩個數做遞歸的結果合併,就是ans(反覆此步驟)

class Solution(object):
    def permute(self, nums):
        if len(nums)<=1:     #nums的長度小於等於1,回傳nums
            return [nums]
        
        ans=[]
        for i,num in enumerate(nums[:]):
        #先選出來一個出來[1],剩下[2,3],再繼續做遞歸
            n=nums[:i]+nums[i+1:]    
            for j in self.permute(n):
                ans.append([num]+j) #把先選出來的1,跟剩下兩個數做遞歸的結果合併      
        return ans

dfs求解 :

類似於上面解法,但用一個新的function求解

class Solution(object):
    def permute(self, nums):
        ans=[]
        def dfs(nums,tmp,n):
            if len(tmp)==n:      #當暫存等於給的陣列長度時,返回傳存值
                ans.append(tmp[:])
            for i in range(len(nums)):
                tmp.append(nums[i])
                dfs(nums[:i]+nums[i+1:],tmp,n)   #遞歸,把其中一個數剃除,剩下兩個數做遞歸
                tmp.pop()  
        dfs(nums,[],len(nums))
        return ans

C++

backtracking法 :

從第一個位置開始,枚舉所有可能的數,將其與第一個位置交換,然後進入下一層遞歸;在下一層遞歸中,枚舉當前位置之後所有可能的數,將其與當前位置交換,然後進入下一層遞歸;遞歸的結束條件是當前位置已經到達數組末尾,此時將當前排列加入結果集中。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permute(nums, 0, ans);
        return ans;
    }
    
    void permute(vector<int>& nums, int idx, vector<vector<int>>& ans) {
        if (idx == nums.size()) {
            ans.push_back(nums);        #找到解
            return;
        }
        for (int i = idx; i < nums.size(); i++) {
            swap(nums[idx], nums[i]);           #位置交換
            permute(nums, idx+1, ans);          
            swap(nums[idx], nums[i]);      #將交換的數交換回來
        }
    }
};

在該代碼中,permute 函數用於實現回溯算法,其中 nums 表示待排列的整數數組,idx 表示當前位置,ans 表示結果集。如果當前位置已經到達數組末尾,將當前排列加入結果集中。否則,枚舉當前位置之後所有可能的數,並交換當前位置與枚舉的數,然後進入下一層遞歸。遞歸結束後,需要將交換的數交換回來,以便進行下一次枚舉。