subset 문서

이 문제는 backtracking 문제로도 유명하지만 데이터의 수가 많아지는 경우 dp 로 해결할 수 있습니다.

(예시) A = { 1 , 2 , 3}

집합 A 의부분 집합 중 원소 3 을 포함하는 부분 집합은 어떻게 구할 수 있을까요?

답) A = {1, 2} 의 부분 집합

• {}
• 1
• 2
• 1,2

에서 각각에 3 을 더한 4 개가 됩니다.

• {} + 3
• 1 + 3
• 2 + 3
• 1,2 + 3

이 와 같은 방법으로 확장이 이루어 집니다.

---구현

• 시작 상태

  

• 원소 1 이 적용된 상태 입니다.

  

• 원소 2 가 적용된 상태 입니다. 2 번 적용되는 것을 막기 위하여 뒤에서 앞으로 검사 합니다.

  

• 원소 3 이 적용되는 과정 입니다.
  •  

    

  •  

    

  •  

    

  •  

    

2.소스

3.시간 복잡도

관련 문제:구슬 게임, 돌다리 건너기, 연속적인 소수의 합, 줄다리기, 스파이더 맨, 가장 긴 접두어, 만들수 없는 수