본 문서에서는 백트래킹(Backtracking) 알고리즘을 사용하여 LeetCode의 세 가지 문제를 해결하는 방법을 설명합니다. 각 문제에 대한 핵심 아이디어와 함께 Java 코드를 제공하며, 코드의 구조와 로직을 변경하여 유사성을 줄이고자 했습니다.
1. LeetCode 491: 증가하는 부분 수열 (Non-decreasing Subsequences)
주어진 정수 배열에서 길이가 2 이상인 모든 증가하는 부분 수열을 찾아야 합니다. 동일한 부분 수열이 결과에 중복으로 포함되어서는 안 됩니다.
백트래킹을 통해 가능한 모든 부분 수열을 탐색하되, 새로운 요소를 추가할 때 이전 요소보다 크거나 같아야 한다는 조건을 만족시켜야 합니다. 또한, 동일한 레벨(깊이)에서 같은 숫자가 여러 번 사용되는 것을 방지하기 위해 각 레벨마다 `HashSet`을 사용하여 중복을 제거합니다.
import java.util.*;
class Solution491 {
private List<Integer> currentSubsequence = new LinkedList<>();
private Set uniqueSubsequences = new HashSet<>();
public List findSubsequences(int[] nums) {
backtrack(nums, 0);
return new ArrayList<>(uniqueSubsequences);
}
private void backtrack(int[] nums, int startIndex) {
if (currentSubsequence.size() >= 2) {
uniqueSubsequences.add(new ArrayList<>(currentSubsequence));
}
// 현재 탐색 깊이에서의 중복 숫자 방지
Set<Integer> usedInLevel = new HashSet<>();
for (int i = startIndex; i < nums.length; i++) {
// 증가하는 조건 확인 또는 이미 사용된 숫자인지 확인
if (!currentSubsequence.isEmpty() && currentSubsequence.get(currentSubsequence.size() - 1) > nums[i]) {
continue;
}
if (usedInLevel.contains(nums[i])) {
continue;
}
usedInLevel.add(nums[i]);
currentSubsequence.add(nums[i]);
// 재귀 호출 시 다음 인덱스부터 탐색
backtrack(nums, i + 1);
// 백트래킹: 마지막 요소를 제거하여 이전 상태로 복구
currentSubsequence.remove(currentSubsequence.size() - 1);
}
}
}
2. LeetCode 46: 순열 (Permutations)
서로 다른 원소를 포함하는 배열이 주어졌을 때, 가능한 모든 순열을 반환해야 합니다.
이 문제는 모든 요소를 사용하는 완전 탐색을 통해 해결할 수 있습니다. 각 단계에서 아직 사용되지 않은 숫자를 선택하여 현재 순열에 추가하고, 재귀적으로 다음 단계를 진행합니다. 사용된 숫자는 별도의 배열이나 집합을 통해 추적합니다.
import java.util.*;
class Solution46 {
private List<Integer> currentPermutation = new LinkedList<>();
private List allPermutations = new ArrayList<>();
private boolean[] usedElements;
public List permute(int[] nums) {
usedElements = new boolean[nums.length];
generatePermutations(nums);
return allPermutations;
}
private void generatePermutations(int[] nums) {
// 순열의 길이가 원본 배열의 길이와 같으면 결과 리스트에 추가
if (currentPermutation.size() == nums.length) {
allPermutations.add(new ArrayList<>(currentPermutation));
return;
}
for (int i = 0; i < nums.length; i++) {
// 아직 사용되지 않은 숫자만 선택
if (!usedElements[i]) {
currentPermutation.add(nums[i]);
usedElements[i] = true; // 현재 숫자 사용 표시
// 재귀 호출
generatePermutations(nums);
// 백트래킹: 마지막 숫자 제거 및 사용 표시 해제
usedElements[i] = false;
currentPermutation.remove(currentPermutation.size() - 1);
}
}
}
}
3. LeetCode 47: 중복 순열 (Permutations II)
중복된 원소를 포함할 수 있는 배열이 주어졌을 때, 가능한 모든 고유한 순열을 반환해야 합니다.
이전 문제와 유사하지만, 중복을 허용하는 배열의 경우 동일한 순열이 여러 번 생성될 수 있습니다. 이를 방지하기 위해 배열을 먼저 정렬한 후, 백트래킹 과정에서 이전 단계와 같은 숫자를 사용하되 해당 숫자가 아직 사용되지 않았다면 건너뛰는 조건을 추가합니다. 이는 같은 레벨에서 동일한 숫자가 여러 번 시작점으로 선택되는 것을 방지합니다.
import java.util.*;
class Solution47 {
private List<Integer> currentPermutation = new LinkedList<>();
private List uniquePermutations = new ArrayList<>();
private boolean[] usedStatus;
public List permuteUnique(int[] nums) {
Arrays.sort(nums); // 중복 제거를 위해 정렬
usedStatus = new boolean[nums.length];
buildUniquePermutations(nums);
return uniquePermutations;
}
private void buildUniquePermutations(int[] nums) {
if (currentPermutation.size() == nums.length) {
uniquePermutations.add(new ArrayList<>(currentPermutation));
return;
}
for (int i = 0; i < nums.length; i++) {
// 이미 사용된 요소는 건너뜀
if (usedStatus[i]) {
continue;
}
// 중복 제거 조건: 현재 숫자와 이전 숫자가 같고, 이전 숫자가 사용되지 않았다면 건너뜀
if (i > 0 && nums[i] == nums[i - 1] && !usedStatus[i - 1]) {
continue;
}
currentPermutation.add(nums[i]);
usedStatus[i] = true;
buildUniquePermutations(nums);
usedStatus[i] = false;
currentPermutation.remove(currentPermutation.size() - 1);
}
}
}