백트래킹 알고리즘 활용: 증가하는 부분 수열, 순열, 중복 순열 문제 해결

본 문서에서는 백트래킹(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);
        }
    }
}

태그: java 백트래킹 알고리즘 순열 부분 수열

10월 29일 18:26에 게시됨