문제

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

제한사항

• 1 $\leq$ candidates.length $\leq$ 30
• 1 $\leq$ candidates[i] $\leq$ 200
• All elements of candidates are distinct.
• 1 $\leq$ target $\leq$ 500

접근

중복되지 않는 숫자의 집합과 target이 주어졌을 때, 부분 집합의 합이 target이 되는 부분 집합들을 구하는 문제였어요. 여기서 숫자들을 중복 사용이 가능하다는 조건이 있었어요. target이 8이라면 숫자들을 중복 사용, 예를 들면 [2, 2, 2, 2] 조합도 정답에 포함되는 것이죠.

BFS 개념을 사용하면 문제없이 풀 수 있었어요. 어차피 candidates의 개수는 30개 이하니까 시간복잡도를 크게 생각할 필요도 없었어요.

저는 구조체 클래스를 생성해서 구성된 부분 집합과 불필요한 합 연산을 줄이기 위해 부분 집합의 합 그리고 인덱스를 넣어서 전개했습니다. 인덱스를 넣은 이유는 부분 집합을 구성할 때 현재 인덱스를 기준으로 부분집합을 차례로 구성하여 중복 연산을 최소화하기 위해서에요. 정답 변수에 중복된 부분 집합들을 넣을 수 없도록 막을 수도 있고요. 이렇게 해서 문제를 풀었습니다.

여담이지만 빠른 시간에 Medium 난이도를 푼건 이번이 처음이네요 ㅋㅋ. 성장하고 있는게 느껴집니다.

답안

class Solution {
    

    private class CombinationInfo {
        public int offsetIndex;
        public List<Integer> subset = new ArrayList<>();
        public int total;

    }


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> answer = new ArrayList<>();

        Queue<CombinationInfo> queue = new LinkedList<>();
        for(int index = 0; index < candidates.length; ++index){
            CombinationInfo info = new CombinationInfo();
            info.offsetIndex = index;
            info.subset.add(candidates[index]);
            info.total = candidates[index];
            queue.add(info);
        }

        while(!queue.isEmpty()){
            CombinationInfo info = queue.poll();

            if(info.total == target){
                answer.add(info.subset);
            }

            for(int index = info.offsetIndex; index < candidates.length; ++index){
                if(info.total + candidates[index] > target)
                    continue;
                
                CombinationInfo info2 = new CombinationInfo();
                info2.offsetIndex = index;
                info2.subset = new ArrayList<>(info.subset);
                info2.subset.add(candidates[index]);
                info2.total = info.total + candidates[index];
                queue.add(info2);
            }
        }

        return answer;
    }
}