Leetcode 46. 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 表示結果集。如果當前位置已經到達數組末尾，將當前排列加入結果集中。否則，枚舉當前位置之後所有可能的數，並交換當前位置與枚舉的數，然後進入下一層遞歸。遞歸結束後，需要將交換的數交換回來，以便進行下一次枚舉。