[Leetcode] 46. Permutations 문제 풀이

https://leetcode.com/problems/permutations/

Permutations - LeetCode

 

문제 내용

주어진 숫자 배열에서 모든 조합을 구하는 문제

 

Example 1:

Input: nums = [1,2,3]

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

 

문제 풀이

divide & conquer 방식으로 풀었다.

N개의 길이가 있을 때, N개의 모든 조합을 출력하게 했다.

N개중에 하나를 택하면, N-1개의 수가 남는다.

N-1개로 분할된 것을 다시 돌리면 된다.

N-1의 모든 조합에 1개를 모두 추가하는 방식으로 구했다.

class Solution {
public:
    vector<vector<int>> per(vector<int>& nums, vector<bool>& visit, int size) {
        vector<vector<int>> ans;
        
        if (size == nums.size() - 1) {
            for (int i = 0; i < nums.size(); ++i) {
                if (visit[i])
                    continue;
                ans.push_back({nums[i]});
            }
        }
        else {
            for (int i = 0; i < nums.size(); ++i) {
                if (visit[i])
                    continue;

                visit[i] = true;

                auto child = per(nums, visit, size+1);
                for (auto& c : child) {
                    c.insert(c.begin(), nums[i]);
                    ans.push_back(c);
                }

                visit[i] = false;
            }
        }
        
        return ans;
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visit(nums.size(), false);
        return per(nums, visit, 0);
    }
};