Permutations
LeetCode의 Permutations 문제를 함께 풀어보도록 하겠습니다.
문제
중복되지 않은 정수의 목록이 주어졌을 때, 모든 가능한 순열을 구하라.
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]풀이
일반적으로 순열을 구할 때 실제 어떻게 사고를 하는지 생각을 해보겠습니다. 아래와 같이 3개의 정수가 주어졌다면,
[1, 2, 3]- 먼저
1을 선택하면[2, 3]이 남습니다. - 남은 정수 중에서
2를 선택하면,[3]이 남습니다. - 남은 정수 중에서
3을 선택하면 아무 것도 남지 않습니다.
이렇게 첫번째 순열을 구했습니다.
[1, 2, 3]위의 두번째 과정으로 다시 거슬러 올라가 2 대신에 3을 선택합니다.
마지막에 남은 정수는 2였을 것이므로, 두번재 순열은 다음과 같이 구해집니다.
[1, 3, 2]이제 두번째 과정으로 거슬러 올러가더라도 2와 3을 모두 선택을 했었기 때문에 더 이상 선택의 여지가 없습니다.
따라서 첫번쨰 과정으로 거슬러 올라가,
1대신에2를 선택하면[1, 3]이 남습니다.- 남은 정수 중에서
1를 선택하면,[3]이 남습니다. - 남은 정수 중에서
3을 선택하면 아무 것도 남지 않습니다.
이렇게 세번째 순열을 구했습니다.
[2, 1, 3]네번째 순열을 구할 때는 두번쨰 과정을 거슬러 올라가 1 대신에 3을 선택할테고,
다셋번째 순열을 구할 때는 첫번째 과정을 거슬러 올라가 2 대신에 3을 선택할 것입니다.
이러한 과정을 더 이상 선택의 여지가 없을 때까지 반복하면 모든 순열을 구할 수가 있습니다. 이렇게 이전 단계에서 전에 넣었던 값을 빼고 다음 값을 넣는 기범을 소위 백트랙킹(backtracking)이라고 합니다.
따라서 이 문제는 백트랙킹과 재귀 알고리즘을 이용해서 위의 로직을 구현하면 해결할 수 있습니다.
Java
results에는 순열의 목록을, path에는 정수의 목록을 저장합니다.
남은 정수가 없을 때, 최종 순열을 results에 추가합니다.
순열에 정수를 넣은 후에 재귀 함수를 호출 하고 다시 정수를 빼기 위해서 스택 자료구조를 사용합니다.
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList();
helper(results, new Stack(), nums);
return results;
}
private void helper(List<List<Integer>> results, Stack<Integer> path, int[] nums) {
if (path.size() == nums.length) {
results.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (path.contains(nums[i])) continue;
path.push(nums[i]);
helper(results, path, nums);
path.pop();
}
}
}Python
파이썬을 이용하면 매우 유연한 내장 리스트 덕분에 좀 더 간결한 코드를 작성할 수 있습니다.
class Solution:
def permute(self, nums):
results = []
def helper(path, nums):
if not nums:
return results.append(path)
for i in range(len(nums)):
helper(path + [nums[i]], nums[:i] + nums[i + 1:])
helper([], nums)
return results