[알고리즘] Leetcode_39_Combination_Sum

Problem

Solve

class Solution {
    public void backtracking(int[] candidates, List<List<Integer>> result, List<Integer> list, int sum, int index, int target){
        if(sum > target || index == candidates.length){
            return;
        }
        if(sum == target){
            result.add(new ArrayList<>(list));
            return;
        }

        for(int i = index ; i < candidates.length; i++){
            list.add(candidates[i]);
            sum += candidates[i];
            backtracking(candidates, result, list, sum, i, target);

            list.remove(list.size()-1);

            sum -= candidates[i];

        }
        
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>(); //반환 결과값

        backtracking(candidates, result, new ArrayList<>(), 0,0, target);
        return result;
    }
}

앞서 배웠던 백트래킹(조합)에서 중복을 허용하는 기능을 추가한 것이다.

• 중복 허용을 하나 순서는 없는 index 처리 ➡️ 순열은 아닌 중복 조합이다. 즉 [2,2,3]이나 [2,3,2], [3,2,2] 는 같다는 것! 그렇기 때문에 index 는 현재 원소를 포함하기 때문에 그대로 index를 넘겨준다.

• base case 를 위해 sum 이 target 을 넘어가는 순간을 어떻게 처리를 해야할 것인지 ➡️ 그냥 return

• sum 과 list의 원소 값을 어떻게 처리해야 할 것인지 ➡️ 다음 원소 (for문 안의 다음 i 값) 을 위해 backtracking 을 다녀온 list에서는 현재 원소 값을 삭제하고, sum 에는 현재 원소 값을 빼주면 원상복귀가 되는 것이다.

그치만, 더 애를 먹었던 것은

if(sum == target){
	result.add(list);
}

new ArrayList<>(list) 대신 list 를 써주면 왜 통과가 되지 않는냐는 것이다.

chat GPT 에게 물어보니 통과가 된다고 하지만 , 난 안 됐는걸?
그래서 다시 물어보니 !

list 가 변경되면 result 에 저장된 조합들도 함께 변경될 수 있기 때문에 오류 발생 가능성이 있다고 한다. 따라서 리스트를 복사하는 new ArrayList<>()를 다시 하는 것이 독립적으로 관리할 수 있기 때문에 가장 안전한 방법이라고 한다.

너무 chat GPT 를 맹신해서는 안되겠다는 생각을 함께! 조합과 순열을 여러가지로 응용할 수 있는 것이 신기하고 재밌다.