LeetCode 90(Subsets II, Python)

1. 문제 링크

• Subsets II - LeetCode

Subsets II - LeetCode

2. 문제 설명

• 중복된 숫자가 포함된 배열이 주어질 때, 해당 배열의 모든 부분집합을 나열하는 문제
• 예시) [1, 2, 2]이 주어지면 [[],[1],[1,2],[1,2,2],[2],[2,2]]를 반환

3. 처음 풀이

• 백트래킹 이용
• 백트래킹이 익숙해진 줄 알았는데 상황에 따라 머리가 잘 안돌아간다.
• 스스로 풀지 못해서 Subsets1 문제의 풀이를 참고하여 풀었다.

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 입력 배열을 정렬
        nums.sort()
        # 결과를 저장할 리스트, 빈 리스트로 초기화하여 빈 부분집합 포함
        result = [[]]

        def backtracker(nums, path, idx):
            # 종료 조건: 현재 인덱스가 배열의 길이와 같으면 종료
            if idx == len(nums):
                return
            
            # 현재 인덱스부터 끝까지 반복
            for i in range(idx, len(nums)):
                # 현재 숫자를 부분집합에 추가
                path.append(nums[i])
                # 결과에 중복되지 않는 부분집합 추가
                if path not in result:
                    result.append(path[:])
                # 재귀 호출: 현재 인덱스보다 1 큰 값으로 다음 원소에 대한 부분집합 생성
                backtracker(nums, path, i + 1)
                # 백트래킹: 현재 숫자를 제거하여 다른 부분집합 생성을 위해
                path.pop()
            
        # 백트래킹 시작
        backtracker(nums, [], 0)

        return result

4. 다른 풀이

• 좀 더 간결한 백트래킹

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 입력 배열을 정렬
        nums.sort()
        # 결과를 저장할 리스트
        result = []

        def backtracker(path, idx):
            # 현재 부분집합을 결과에 추가
            result.append(path[:])
            # 현재 인덱스부터 끝까지 반복
            for i in range(idx, len(nums)):
                # 중복 부분집합 생성 방지
                if idx < i and nums[i] == nums[i - 1]:
                    continue
                # 현재 숫자를 부분집합에 추가
                path.append(nums[i])
                # 재귀 호출: 다음 원소에 대한 부분집합 생성을 위해 인덱스 증가
                backtracker(path, i + 1)
                # 백트래킹: 현재 숫자를 제거하여 다른 부분집합 생성을 위해
                path.pop()

        # 백트래킹 시작
        backtracker([], 0)

        return result

5. 배운 점

• 아직은 백트래킹으로 푸는 문제가 종종 헷갈림. 쉽게 풀리는 상황도 있는데 잘 안풀릴 때도 있음. 
• 대표적인 백트래킹 문제의 모범 답안들을 모아두고 눈에 익히자

콤비네이션1

def combine(self, n, k):
    res = []
    self.dfs(xrange(1,n+1), k, 0, [], res)
    return res
    
def dfs(self, nums, k, index, path, res):
    #if k < 0:  #backtracking
        #return 
    if k == 0:
        res.append(path)
        return # backtracking 
    for i in xrange(index, len(nums)):
        self.dfs(nums, k-1, i+1, path+[nums[i]], res)

 

퍼뮤테이션1

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.dfs(nums, [], res)
        return res

    def dfs(self, nums, path, res):
        if not nums:
            res.append(path)
            #return # backtracking
        for i in range(len(nums)):
            self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

 

퍼뮤테이션2

def permuteUnique(self, nums):
    res, visited = [], [False]*len(nums)
    nums.sort()
    self.dfs(nums, visited, [], res)
    return res
    
def dfs(self, nums, visited, path, res):
    if len(nums) == len(path):
        res.append(path)
        return 
    for i in xrange(len(nums)):
        if not visited[i]: 
            if i>0 and not visited[i-1] and nums[i] == nums[i-1]:  # here should pay attention
                continue
            visited[i] = True
            self.dfs(nums, visited, path+[nums[i]], res)
            visited[i] = False

 

서브셋1

def subsets1(self, nums):
    res = []
    self.dfs(sorted(nums), 0, [], res)
    return res
    
def dfs(self, nums, index, path, res):
    res.append(path)
    for i in xrange(index, len(nums)):
        self.dfs(nums, i+1, path+[nums[i]], res)

 

서브셋2

def subsetsWithDup(self, nums):
    res = []
    nums.sort()
    self.dfs(nums, 0, [], res)
    return res
    
def dfs(self, nums, index, path, res):
    res.append(path)
    for i in xrange(index, len(nums)):
        if i > index and nums[i] == nums[i-1]:
            continue
        self.dfs(nums, i+1, path+[nums[i]], res)

 

콤비네이션 썸

def combinationSum(self, candidates, target):
    res = []
    candidates.sort()
    self.dfs(candidates, target, 0, [], res)
    return res
    
def dfs(self, nums, target, index, path, res):
    if target < 0:
        return  # backtracking
    if target == 0:
        res.append(path)
        return 
    for i in xrange(index, len(nums)):
        self.dfs(nums, target-nums[i], i, path+[nums[i]], res)

 

콤비네이션 썸2

def combinationSum2(self, candidates, target):
    res = []
    candidates.sort()
    self.dfs(candidates, target, 0, [], res)
    return res
    
def dfs(self, candidates, target, index, path, res):
    if target < 0:
        return  # backtracking
    if target == 0:
        res.append(path)
        return  # backtracking 
    for i in xrange(index, len(candidates)):
        if i > index and candidates[i] == candidates[i-1]:
            continue
        self.dfs(candidates, target-candidates[i], i+1, path+[candidates[i]], res)