46. Permutations

題目網址：https://leetcode.cn/problems/permutations/

題意：給一不含重複數字的 array nums, 求所有可能的排列, 以任意順序返回。

Solution：

想法：DFS, nums[i] 輪流當頭

e.g. nums = [1, 2, 3]

• 1 當頭 : [1, 2, 3], [1, 3, 2]

• 2 當頭 : [2, 1, 3], [2, 3, 1]

• 3 當頭 : [3, 2, 1], [3, 1, 2]

  

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums, 0, nums.size());
        return res;
    }

private:
    vector<vector<int>> res;

    void dfs(vector<int>& nums, int i, int n){
        if (i == n) {
            res.emplace_back(nums);
            return;
        }

        for (int j = i; j < n; ++j) {
            swap(nums[i], nums[j]);
            dfs(nums, i + 1, n); // 跟開頭 nums[i] 做 swap, 排序 i + 1 (開頭以後)
            swap(nums[i], nums[j]);
        }
    }
};

• time：$O(n \cdot n!)$ ➔ 總共 $n!$ 種排列, 建構每一種排列皆需花 $O(n)$ time
• space：$O(n)$ ➔ 若不考慮要返回的 array, 則取決於遞迴的最大深度