재귀2

• 

  LeetCode #77. Combinations(조합) 2가지 DFS로 풀어보자! 고민- 이미 사용된 숫자는 어떻게 제외하고, 다음 재귀 시 재활용할 것인가?위 고민에 사로잡혀, 맨처음엔 Queue를 활용하여 풀이 방법 2번으로 풀었다. 하지만 책에서 제안한 풀이법을 보니, 굳이 Queue를 통해 남아있는 숫자를 관리하지 않아도 되고, 단순한 반복을 통해 풀이할 수 있다는 것을 알 수 있었다. 풀이 방법 간의 속도 차이도 큰 편이었다.문제 설명1부터 ( n )까지의 정수에서 ( k ) 개의 숫자를 선택하여 가능한 모든 조합(combination)을 반환하라. 조합은 선택된 원소들의 순서를 고려하지 않는다.입력 및 출력 예시Example 1:Input: n = 4, k = 2Output: [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]Example.. Java/Algorithm 2024. 8. 6.

• 

  LeetCode #46. Permutations(순열) DFS(백트래킹, 재귀)로 풀어보자! 문제 설명정수 배열 nums가 주어졌을 때, 가능한 모든 순열(permutation)을 반환하라. 순열은 원소들의 모든 가능한 순서를 의미한다.입력 및 출력 예시Example 1:Input: nums = [1, 2, 3]Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]Example 2:Input: nums = [0, 1]Output: [[0, 1], [1, 0]]Example 3:Input: nums = [1]Output: [[1]]제약사항1 -10 nums의 모든 원소는 고유하다.풀이 1: 백트래킹 (Backtracking) 사용시간 복잡도시간복잡도: O(n * n!) (n은 배열의 길이)T(n)=n!×(c1​×n + .. Java/Algorithm 2024. 8. 3.