[LeetCode] Subsets(부분집합)

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

Subsets - LeetCode

• 문제 설명
  • 부분집합을 구하는 문제이다.
  • [1,2,3] 리스트가 주어졌을때 총 [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] 을 출력하면 된다.

---

Stack, DFS 활용

• 종료조건 : 주어진 리스트와 부분집합을 구하면서 길이가 같아지면 반환한다.

            if len(stack) == len(nums):
                if sorted(stack) not in output:
                    output.append(sorted(stack))
                    return

• 리스트에 요소를 하나하나씩 가져와 stack에 없다면 stack에 추가해준다.

            for w in nums:
                if w not in stack:
                    if sorted(stack) not in output:
                        output.append(sorted(stack))
                    dfs(stack + [w])

문제점

• 예를 들면 [1,3] [3,1]은 같은데 sorted로 다시 정렬해 중복인지 아닌지 확인 시간이 추가된다.
• 그래서 중복되더라도 요소를 하나씩 다 리스트로 만들어 확인하기 때문에 시간이 오래걸림

 

DFS(깊이 우선 탐색)

• 종료조건 : 주어진 리스트와 부분집합의 길이가 같아지면 반환한다.
• 재귀함수를 호출하는 조건 
  
  • 값을 넘길때 해당 인덱스 요소의 증가값과 부분집합을 추가한 스택을 같이 넘겨줘야 한다.

class Solution:
    def subsets_dfs_2(nums):
        result = []

        def dfs(index, path):
            result.append(path)
            print(result)
            for i in range(index, len(nums)):
                dfs(i+1, path+[nums[i]])
        dfs(0, [])
        return result

1) dfs(0, []) result=[[]] i = 0 일때 dfs(1, []) 호출

2) dfs(1, [1]) result = [[],[1]] i = 1일때 dfs(2, [1]+[2]) 호출

3) dfs(2, [1,2]) result = [[],[1],[1,2]] i = 2일때 dfs(3, [1,2]+[3] 호출

4) dfs(3, [1,2,3]) result = [[],[1],[1,2],[1,2,3]] for 문을 진행 할 수 없음으로 반환

 

-----4) 종료되어 3)으로 돌아온다 3)도 for문이 끝났음으로 2)로 반환된다.

현재, result = [[],[1],[1,2],[1,2,3]]

5) dfs(1,[1]) i= 1은 진행했기 때문에 i = 2 일때 dfs(3, [1]+[3]) 호출

6) dfs(3,[1,3]) result = [[],[1],[1,2],[1,2,3], [1,3]] for문은 진행 할 수 없다.

 

-----6) 종료 5)로 돌아온다해도 for문이 끝났음으로 1)로 반환된다.

현재, result = [[],[1],[1,2],[1,2,3], [1,3]]

7) dfs(0,[]) i = 1 일때 진행 dfs(2,[]) 호출

...(생략)