[LeetCode] 78. Subsets

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

Algorithm

로직을 완전히 이해하는데 반나절 걸린 문제이다.ㅎ... 이 문제의 핵심은 백트래킹! 모든 집합 경우의 수 탐색이므로, 이진트리를 사용한다.여기서는 백트래킹을 이용하고, 알고리즘 두가지로 풀어볼 것이다.

먼저 첫번째 방법은 위와같은 구조로 각 가능한 경우수를 세는 방법이다!

처음 떠올린 로직이다.

이건 풀이를 참조했는데, 각 숫자를 선택하는 경우 / 선택안하는경우로 케이스를 나누어 탐색하는 방법이다.

 

*주의할점

path[:]를 사용하면 path 리스트의 현재 상태를 복사하여 추가한다. 이렇게 하면 후에 path가 변경되더라도 result 리스트에 추가된 path는 영향을 받지 않는다. 즉, 각 재귀 호출에서 다른 path를 가리키게 되어 결과가 올바르게 나온다.

헷갈린다면 아래 예시를 보자

path = [1, 2]
result = []

# 처음에는 path[:]를 사용하지 않고 추가하는 경우
result.append(path)
print(result)  # 출력: [[1, 2]]

# 이제 path를 변경합니다.
path.append(3)

# result
print(result)  # 출력: [[1, 2, 3]]

# 하지만 원래의 결과는 변하지 않았어야 합니다.
print(path)    # 출력: [1, 2, 3]

---

Python

class Solution:
    def subsets(self, nums):
        def dfs(s, path):
            result.append(path) # path 추가

            if len(path) == n: # 종료조건
                return

            for i in range(s, n):
                if nums[i] not in path:
                    path.append(nums[i])
                    dfs(i+1, path[:])
                    path.pop()

        result = []
        n = len(nums)
        backtrack(0, [])
        return result

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i):
            if i >= len(nums): # 종료 조건
                res.append(subset.copy())
                return
            # nums[i] 선택하는 경우
            subset.append(nums[i])
            dfs(i + 1)
            # nums[i] 선택하지 않는 경우
            subset.pop()
            dfs(i + 1)
        
        dfs(0)
        return res

Java

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        dfs(0, new ArrayList<>(), nums, result);
        return result;
    }
    
    private void dfs(int s, List<Integer> path, int[] nums, List<List<Integer>> result){
        result.add(new ArrayList<>(path)); // path 복사하여 추가

        if(path.size() == nums.length) return; // 종료조건

        for(int i = s; i < nums.length; i++){
            if(!path.contains(nums[i])){
                path.add(nums[i]);
                dfs(i + 1,new ArrayList<>(path), nums, result);
                path.remove(path.size() - 1);
            }
        }
    }
}

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        dfs(ans, 0, nums, list);
        return ans;   
    }
    public void dfs(
        List<List<Integer>> ans,
        int start,
        int[] nums,
        List<Integer> list
    ) {
        if(start >= nums.length){
            ans.add(new ArrayList<>(list)); // 복사해 경로 추가
        } else {
            list.add(nums[start]);
            dfs(ans, start + 1, nums, list); // 현재노드 포함
            list.remove(list.size() - 1); // 현재노드 미포함
            dfs(ans, start + 1, nums, list);
        }
    }
}