[LeetCode] Permutations

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

 

먼저 순열을 어떻게 구할 지 방법을 선택해야 합니다. 저는 재귀적인 방법을 선택해서 문제를 풀었습니다. 

start = 0	start = 1	start = 2
[1, 2, 3]	[1, 2, 3]	[1, 2, 3]
	[1, 3, 2]	[1, 3, 2]
[2, 1, 3]	[2, 1, 3]	[2, 1, 3]
	[2, 3, 1]	[2, 3, 1]
[3, 2, 1]	[3, 2, 1]	[3, 2, 1]
	[3, 1, 2]	[3, 1, 2]

순서가 보장되어야 ok 되는 것은 아니더라구요. 가능한 모든 순열을 저장한 배열을 반환하면 됩니다. 그래서 모든 경우의 수를 구할 수 있는 코드를 작성해 보았습니다. start index와 i index를 바꿔주면서 계산을 진행했습니다. 

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