[Grind75-LeetCode] Combination Sum JAVA

반응형

728x90

[Grind75-LeetCode] Combination Sum - Medium

---

접근

• dfs

---

풀이

주어지는 정수 배열의 요소들을 사용해 target을 만들 수 있는 모든 조합을 구하는 문제이다. 배열에는 중복된 원소가 존재하지 않고 각 요소를 무한히 사용이 가능하다. 전에 풀었던 동전 문제와 유사하나 이번에는 최소 개수를 구하는 것이 아닌 모든 조합을 구해야 하므로 dfs를 사용해 풀어주었다. 

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> ls = new ArrayList<>();
        dfs(candidates, target, 0, ls, result);
        
        return result;
    }

결과를 반환할 리스트와 각 조합을 저장할 리스트를 선언하고 dfs를 수행한다. dfs는 재귀를 이용해 간단히 구현되었다.

    public void dfs(int[] candidates, int target, int current, List<Integer> ls, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for (int i = current; i < candidates.length; i++) {
            if (target >= candidates[i]) {
                ls.add(candidates[i]); 
                dfs(candidates, target - candidates[i], i, ls, res); 
                ls.remove(ls.size() - 1); 
            }
        }
    }

dfs 메서드로 target의 값을 줄여 0을 만드는 방식으로 진행했다. target이 0이 되면 조합이 완성된 것이므로 결과 리스트에 추가한다. 그렇지 않다면 배열을 순회하며 target의 값이 현재 요소보다 클 경우 조합에 추가하고 다음 dfs를 호출해준다. 호출이 끝나면 추가되었던 요소를 제거해 다른 경로를 다시 재탐색할 수 있게 만들어 준다. 

dfs

재귀를 통해 해결했다보니 1ms로 해결이 가능했다. 

---

전체 코드

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> ls = new ArrayList<>();
        dfs(candidates, target, 0, ls, result);
        
        return result;
    }

    public void dfs(int[] candidates, int target, int current, List<Integer> ls, List<List<Integer>> res) {
        if (target == 0) {
            res.add(new ArrayList<>(ls));
            return;
        }
        for (int i = current; i < candidates.length; i++) {
            if (target >= candidates[i]) {
                ls.add(candidates[i]); 
                dfs(candidates, target - candidates[i], i, ls, res); 
                ls.remove(ls.size() - 1); 
            }
        }
    }
}