LeetCode: 39번 (Combination Sum) [JAVA]

문제 링크

https://leetcode.com/problems/combination-sum/

Combination Sum - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 완전탐색을 기반으로 target에 대해 가능한 조합을 만드는 함수를 재귀호출을 바탕으로 작성
   • 인자는 candidates 배열과 target 중 현재 남은 값을 나타내는 remain 값, candidates 배열 중 현 위치를 나타내는 index 값
   • 기저 조건은 remain이 0이 되는 경우 여태까지 구성한 ArrayList<Integer> 배열을 ArrayList<ArrayList<Integer>>에 추가
   • for문을 바탕으로 index 위치부터 candidates 배열을 돌며 해당 값이 remain 보다 작으면 현 위치와 remain에서 해당 값을 뺀 만큼을 인자로 다음 함수 호출
2. 탐색 종료 후 여태까지 조합을 누적한 ArrayList<ArrayList<Integer>>을 반환

 주어진 target 값을 만들 수 있는 숫자들의 조합을 candidates 배열에서 찾아 그 리스트들을 반환해야 하는데, 조건 자체는 복잡하지만 주어진 조건 상 복잡도가 그리 크지 않기 때문에 완전탐색을 기반으로한 재귀호출 함수를 작성한다.

 함수의 인자는 주어진 candidates 배열과 target 값 중 남은 값을 나타내는 remain 값, 그리고 candidates 배열 중 현 위치를 나타내는 index로 하고, 기저 조건은 remain 값이 0이 된 경우로 한다. 그리고 단순히 함수 내부에선 candidates 배열을 index 위치부터 탐색을 시작해 해당 값이 remain보다 작다면 다음 함수를 호출하며 remain에서 현재 값을 뺀 나머지와 현 위치를 index의 인자로 넣으면 된다.

 

class Solution {
    ArrayList<Integer> list = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();//clone() 함수 활용

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        generateComb(candidates, target, 0);
        return result;
    }

    void generateComb(int[] candidates, int remain, int index) {
        if (remain == 0) {//조합이 완성된 경우
            result.add((ArrayList<Integer>) list.clone());
        }

        for (int i = index; i < candidates.length; i++) {
            if (candidates[i] <= remain) {//백트래킹 기반 탐색
                list.add(candidates[i]);
                generateComb(candidates, remain - candidates[i], i);
                list.remove(list.size() - 1);
            }
        }
    }
}

결과