[leetcode] 39. Combination Sum - java

39. Combination Sum

문제 LINK : https://leetcode.com/problems/combination-sum/description/

candidates 배열 내 합으로 target이 되는 모든 조합 찾기.

난이도 : medium

문제 풀이

소스

class Solution {
    List<List<Integer>> result;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        result = new ArrayList<>();
        calc(candidates, 0, 0, target, new ArrayList<Integer>());
        return result;
    }
    public void calc (int [] candidates ,int index, int sum, int target, List<Integer> addList){
        //System.out.println(sum);
        if(sum>target){
            return ;
        }
        if(sum==target){
            result.add(new ArrayList<>(addList));
            return;
        }
        for(int i=index;i<candidates.length;i++){
                addList.add(candidates[i]);
                calc(candidates, i, sum+candidates[i], target, addList);
                addList.remove(Integer.valueOf(candidates[i]));
        }
    }
}

해결과정

1. 조합 Combination 으로 해결 1~N 개
   -> 중복된 값을 가질 수 있으며 n개 이상의 조합을 만들어 낼 수 있었다.
2. 재귀
   -> 재귀를 돌면서 sum == target 인 경우 / sum>target 커지면 종료 로 조건을 주고 전체 탐색.
   -> 인데스 없이 돌리다보니 이상하게 답이 틀림..-> 인덱스를 주고 해당 위치 이후로는 다시 탐색이 되지 않도록 함.
   -> 결과값에 저장할 때 단순히 파라미터로 받고 있던 리스트를 바로 저장할 하니 공백으로 답이 나옴. result.add(addList); addList 주소값이 날라가는 듯 합니다.

출력시점의 result

       -> new ArrayList<>(addList) 로 값을 받게 변경함.  
       -> ArrayList 값을 삭제 할 때 .remove() 를 사용하는데, Integer.valueOf(1) => valueOf(값)을 이용해서 Object 가 삭제되게 처리해준다. 단순히 int 값을 넣으면 remove(int index) 로 삭제가 되어버린다.

백트래킹으로 푸는 것으로 접근했으나, 사소한 INDEX나 기본 문법(ArrayList.remove() / add 등) 기초를 다질 필요가 있음.