문제 링크

https://leetcode.com/problems/combinations/

문제 정리

• 입력값 n과 k를 받는다.
• 1~n까지의 숫자에서 k자리만큼 조합 가능한 수를 출력한다.

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

접근방법

• 백트래킹 방식으로 접근할 수 있을것같다.
• 인덱스를 증가시켜 중복값이 없도록 반복한다.
• k만큼의 자릿수가 생성되면 결과값에 추가한다.

코드 진행

• 전체코드

1. 결과값을 저장할 res를 생성한다.

   res = []
   

2. backtrack 함수를 생성해 재귀적으로 접근한다.

   시작 인덱스와 조합한숫자의 리스트를 인자로 받아 진행한다.

   def backtrack(start, comb) :
   

   1. comb에 담긴 길이가 k와 같을 경우 res에 저장한다.

      <aside> 💡 여기서 copy()를 사용한 이유는 복사를 하지 않을 경우 comb의 값을 변경 시 res에 담겨있는 값까지 변하기 때문이다.

      </aside>

      if len(comb) == k :
                  res.append(comb.copy())
                  return
      

   2. 인덱스를 증가시키면서 dfs방식으로 파고든다.

      for i in range(start, n+1) :
                  comb.append(i)
                  backtrack(i+1, comb)
                  comb.pop()