[리트코드] 46. Permutations 순열, 77. Combinations 조합, 78. Subsets 부분집합

46. Permutations 순열

문제

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

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]]

 

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

 

Example 3:

Input: nums = [1]
Output: [[1]]

 

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

 

접근 방법

주의사항

• 순서가 다르면 다른 것으로 인식한다

  • 예를 들어, {1,2}와 {2,1}은 다른 것으로 간주하며, 둘 다 선택 가능하다.

 

• 중복만 조심하면 된다.

  • {1,1} 과 같이 중복된 요소를 포함하는 경우는 제외해야 한다. → 조건문 활용

 

아이디어

nums에 정수가 중복 없이 존재하기 때문에 다른 요소를 고려할 필요 없이 nums를 순회하면서 모든 경우의 순열을 만든다. 백트래킹을 통해 구현할 수 있다.

 

코드 구현

public class Permutations {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> resultList = new ArrayList<>();
        backtracking(new ArrayList<>(), nums, resultList);
        return resultList;
    }

    public List<List<Integer>> backtracking(List<Integer> curr, int[] nums,
                                            List<List<Integer>> resultList) {
        // base case: curr의 길이가 nums의 길이와 같다면 resultList에 현재 순열을 추가한다
        if (curr.size() == nums.length) {
            resultList.add(new ArrayList<>(curr));
        }

        // 백트래킹 처음 원소부터 마지막 원소까지 순회하며 add, 백트래킹, remove 진행한다
        for (int num : nums) {
            // 현재 접근한 원소가 curr에 없다면 해당 원소를 add 한다
            if (!curr.contains(num)) {
                curr.add(num);
                backtracking(curr, nums, resultList);
                // curr에 가장 최근에 접근한 원소를 제거한다
                curr.remove(curr.size() - 1);
            }
        }
        return resultList;
    }
}

• 실행 시간 (Runtime): 2ms

• 메모리 사용량 (Memory): 44.54MB

 

77. Combinations 조합

문제

https://leetcode.com/problems/combinations/description/

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Explanation: There are 4 choose 2 = 6 total combinations.

Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

 

Example 2:

Input: n = 1, k = 1
Output: [[1]]

Explanation: There is 1 choose 1 = 1 total combination.

 

Constraints:

• 1 <= n <= 20
• 1 <= k <= n

 

접근 방법

주의사항

• 순열과는 달리 순서를 고려하지 않는다.

  • 예를 들어, [1, 2]가 선택되었다면, [2, 1]은 중복이므로 제외해야 한다.

• 다음 백트래킹 호출 시 i+1을 넘겨줌으로써 중복을 피하자

 

아이디어

• nums의 개수 n개에서 k개의 원소를 선택하는 문제 유형으로

  • k가 유동적이라 반복문보다 재귀를 많이 사용한다.

 

코드 구현

public class Combinations {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(1, new ArrayList<>(), n, k, result);
        return result;
    }

    public List<List<Integer>> backtracking(int start, List<Integer> curr, int n, int k,
                                            List<List<Integer>> result){
        // base case: curr의 길이가 k와 같으면 현재 조합을 결과 리스트 result 에 추가한다
        if(curr.size() == k) {
            // 현재 조합의 복사본을 추가한다
            result.add(new ArrayList<>(curr));
        }

        // 1부터 n까지 순회하면서 curr에 숫자를 추가하고, 백트래킹을 통해 조합 생성, 삭제를 진행한다.
        for(int i=start; i<=n; i++){
            curr.add(i);
            // [start를 사용하는 이유] 다음 백트래킹을 호출 한다 (i+1을 넘겨줌으로써 중복 방지)
            backtracking(i+1, curr, n, k, result);
            // curr에 가장 최근에 접근한 원소를 제거한다
            curr.remove(curr.size()-1);
        }
        return result;
    }
}

• 실행 시간 (Runtime): 26ms

• 메모리 사용량 (Memory): 94.85MB

 

78. Subsets 부분집합

문제

https://leetcode.com/problems/subsets/description/

Example 1:

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

 

Example 2:

Input: nums = [0]
Output: [[],[0]]

 

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique.

 

접근 방법

• 중간 중간 부분집합을 결과 리스트에 추가하는 과정을 포함해야 한다.

  • 공집합도 포함해야 하므로, 빈 리스트를 처음에 결과 리스트에 추가해야 한다.

 

코드 구현

public class Subsets {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtracking(0, new ArrayList<>(), nums, result);
        return result;
    }

    public List<List<Integer>> backtracking(int start, List<Integer> curr, int[] nums,
                                            List<List<Integer>> result) {
        // base case: 현재 curr 을 결과 리스트 result 에 추가한다. 처음은 []가 추가된다.
        result.add(new ArrayList<>(curr));

        // 원소 처음부터 끝까지 순회하며 add, 백트래킹, remove 를 진행한다
        for(int i=start; i<nums.length; i++){
            curr.add(nums[i]);
            // 재귀 호출을 통해 다음 원소를 추가한 부분집합을 만든다
            backtracking(i+1, curr, nums, result);
            // 부분집합에서 마지막 원소를 제거하여 다음 반복에서 다른 부분집합을 만든다
            curr.remove(curr.size()-1);
        }
        return result;
    }
}

• 실행 시간 (Runtime): 1ms

• 메모리 사용량 (Memory): 42.60MB

 

회고

완전탐색을 순열, 조합, 부분집합을 구현하며 익히는 시간을 가졌다. 셋 다 전부 백트래킹을 사용하지만 각 경우 매개변수로 넘기는 것이 달라 처음에는 헷갈렸다. 지금 당장은 이해하고 넘어갔지만 앞으로도 헷갈릴 가능성이 있기에 한 포스팅으로 정리하게 되었다. 완전탐색은 가장 기본이 되고 자주 사용되기 때문에 여러 번 보고 풀어보면서 익히는 시간을 가져야겠다.