문제

Combinations - LeetCode

Code

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(n, k, new ArrayList<>(), result);
        return result;
    }

    public void dfs(int n, int k, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(path);
            return;
        }

        int start = 1;
        if (path.size() > 0) start = path.get(path.size() - 1) + 1;
        int last = n - k + path.size() + 2;

        for (int i = start; i < last; i++) {
            List<Integer> newPath = new ArrayList<>(path);
            newPath.add(i);
            dfs(n, k, newPath, result);
        }
    }
}

• DFS로 탐색.
• 조합에서는 [1, 2, 3]이랑 [3, 2, 1]은 같은 값이기 때문에 점차 큰 값들을 넣어서 처리하였다.
  

2차 풀이

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(n, k, new ArrayList<>(), result);
        return result;
    }

    public void dfs(int n, int k, List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }

        int start = 1;
        if (path.size() > 0) start = path.get(path.size() - 1) + 1;
        int last = n - k + path.size() + 2;

        for (int i = start; i < last; i++) {
            path.add(i);
            dfs(n, k, path, result);
            path.remove(path.size() - 1);
        }
    }
}

• path.remove(path.size() - 1);
  - 앞에서 넣었던 값을 지워줌으로써 새로운 ArrayList 객체를 만들지 않고 진행하였다.