예를들어
구슬의숫자 N이 3이고
뽑는 개수 M을 2라고 생각해보면
처음에 DFS(0)이 호출되면 중복을 허락하니까
이진트리가 아니라 구슬의 숫자만큼 가지가 생긴다
(1, 1), (1, 2), (1, 3),
(2, 1), (2, 2), (2, 3),
(3, 1), (3, 2) (3, 3)
중복순열은 각각에 대해 모두 중복이 가능하고
순서가 있어서 N^M으로 3^2로 9개이고
M과 N이 4,3이면 64개로
가지가 4(N)개가 되고
레벨이 DFS(0)을 포함해 4(M+1)까지 간다
ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ
res라는 배열에 뽑는 경우의 수 M을
배열 M칸으로 만들고
이진탐색이 아니라 가짓수가 여러개니까
N개만큼의 포문속에서
재귀함수를 실행하면 구슬의 개수만큼 가지를 만든다
부분집합때 처럼 M개가 뽑힐때 까지 돌다가
두개가 뽑히면 출력하는것을 반복한다
댓글 0