16주차. 그래프(조합)

35. 조합

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

Combinations - LeetCode

📌문제

전체 수 n을 입력 받아 k개의 조합을 리턴하라.

- 예제1
  📝입력

n = 4, k = 2

  💻출력

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

📌풀이

9ms, 45.mb

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        combination(result, 1, n, k, 0, new Integer[k]);
        return result;
    }

    public void combination(List<List<Integer>> result, int start, int n, int r, int depth, Integer[] list) {
        if (r == depth) {
            result.add(Arrays.asList(list.clone()));
        } else {
            for (int i = start; i <= n; i++) {
                list[depth] = i;
                combination(result, i+1, n, r, depth + 1, list);
            }
        }
    }
}

 

원래는 방문 여부 배열을 만들어서 체크해줬는데 방식을 새롭게 바꿔봤다. i의 시작 인덱스를 정할 수 있어 방문 배열이 필요 없게 됨