13 Backtracking Algorithm
[실습] Subset Sum 문제
배우기
실습 내용
- subset sum 문제는
n개의 정수로 구성된 집합A와 정수S값이 주어지면, 원소의 합이S가 되는A의 부분 집합이 존재하는지 여부를 결정하는 문제이다 - 여러분은 합이
S가 되는 부분집합을 모두 찾아 출력해야 한다 (A의 값은 우선 오름차순으로 정렬한 후 고려한다) x[0 ... n-1]는 해를 저장하는 리스트로,x[i] = 1이라는 의미는A[i]가 해에 포함된다는 의미이고,x[i] = 0이면 해에 포함되지 않는다는 의미다- 해가 되는 부분 집합을 한 줄에 하나 씩 출력한다: print_subset(x) 함수를 이용한다
- 해가 하나보다 많다면, 이진수 표현에 대한 내림차순으로 한 줄에 하나씩 출력해야 한다
- 예:
A = [1, 2, 3, 4, 5], S = 5 - 해는 두 가지:
x = [1, 0, 0, 1, 0]와x = [0, 1, 1, 0, 0] x = [1, 0, 0, 1, 0]을 10010으로x = [0, 1, 1, 0, 0]을 01100의 이진수로 본다면,10010 > 01100이므로 출력에선[1, 4]이 첫 줄에,[2, 3]을 다음 줄에 출력하면 된다
- 주의: 해가 존재하지 않을 수도 있다. 해가 없는 경우엔 빈 리스트
[]만 출력한다
입/출력 예시
:
공백
:
줄 바꿈
:
탭
예시 1
입력31245
5
5
[1,4]
[2,3]
[5]
[2,3]
[5]
예시 2
입력87653109
15
15
[3,5,7]
[5,10]
[6,9]
[7,8]
[5,10]
[6,9]
[7,8]
예시 3
입력123456789-1-2-3-4-5-6-7-8-9
100
100
[]
⋇ 입출력 형식을 잘 지켜주세요
질문하기
추가 자료
추가 자료가 없습니다
여기서 새로운 학습 자료를 확인하세요!
선생님이 추가한 자료들을 바로 확인할 수 있어요.