#46. Permutations

題目描述

給你一個陣列nums，陣列中的整數都是唯一的，回傳所有可能的排列組合。

你可以回傳任意順序排列的答案。

限制條件

1. 1 <= nums.length <= 6
2. -10 <= nums[i] <= 10
3. 所有整數都是唯一的。

解題思路

排列組合很簡單，從陣列中一次拿取一個元素，直到沒有元素可以拿。

要注意的是，不能出現重複的排列組合，因此我們不能隨意挑選元素，只能按照順序來挑選元素。

執行步驟：

1. 按照順序挑選元素。
   1. 將元素加入到暫時的排列組合陣列中。
   2. 如果是最後一個元素，則將完成的排列組合放進答案中。
   3. 如果陣列元素還有剩餘，則將刪去已經挑選的元素的陣列、暫時的排列組合陣列，放入下一次挑選中處理。
2. 完成所有排列組合。

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        var ans = new List<IList<int>>();
        Helper(nums, new List<int>(), ans);
        return ans;
    }
    public void Helper(int[] nums, List<int> tmp, List<IList<int>> ans){                
        for(int i=0; i<nums.Length;i++){
            var newTmp = new List<int>(tmp);
            newTmp.Add(nums[i]);
            if(nums.Length==1) {
                ans.Add(newTmp);
                return;
            }            
            Helper(nums.Except(new int[]{nums[i]}).ToArray(), newTmp, ans);
        }
    }
}

複雜度分析：

• 時間複雜度：進行排列組合的時候，會花費(n*(n-1))/2的時間，因此時間複雜度為O(n^2)。
• 空間複雜度：呼叫堆疊使用的空間會等於排列組合的長度，因此空間複雜度為O(n)。

學習重點

• Backtracking