# LeetCode Medium 46. Permutations

tags: leetcode

問題

• Explore
• Problems

異なる整数の集まりを与えられたとき, 全てのありうる順列を返せ

解法(recursive)

与えられた配列の順番を色々変えれば良いわけです

下のように全ての添字の組み合わせで要素を交換すれば全てのありうる配列を生成できます

再帰関数を使えばこの処理をすることは難しくありません

• ある要素と要素の位置を入れ替えて, そして再帰的にこの関数を実行します
• そして, さっき入れ替えた要素を元に戻します
• この操作によりある配列から派生する配列を全て表現することが可能です

計算量

配列の長さを$n$とします

• 空間計算量
  • 再帰関数による空間計算量は再帰関数を実行する深さに依存します. これは$O(\log(n))$
  • 答えを格納するのに必要な配列は計算しなくて良いので, $O(\log(n))$
• 時間計算量
  • $0$から配列の長さ分, 要素を入れ替えます
  • つまり, $n, n - 1, \dots, 1$回入れ替えを行います
  • よって$O(n!)$

Python

class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
    def helper(res, nums, begin):
      if begin == len(nums):
        res.append(nums.copy())
        return
      
      for i in range(begin, len(nums)):
        nums[begin], nums[i] = nums[i], nums[begin]
        helper(res, nums, begin+1)
        nums[begin], nums[i] = nums[i], nums[begin]
            
    res = []
    helper(res, nums, 0)
    return res

C++

class Solution {
public:
  vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;
    helper(res, nums, 0);
    return res;
  }
private:
  void helper(vector<vector<int>>& res, vector<int>& nums, int begin) {
    if (begin == nums.size()) {
      res.push_back(nums);
      return;
    }
    for (int i = begin; i < nums.size(); i++) {
      swap(nums[begin], nums[i]);
      helper(res, nums, begin+1);
      swap(nums[begin], nums[i]);
    }
  }
};