39 - Combination Sum

info

• 문제 보기: 39 - Combination Sum
• 소요 시간: 48분 28초
• 풀이 언어: java
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

dfs 조합

풀이 코드

info

• 메모리: 45300 KB
• 시간: 74 ms

class Solution {
    int[] cand;
    int t;
    List<List<Integer>> combList;
    
    public void createComb(int i, int n, int total, List<Integer> candList) {
        //System.out.println(n + " " + total + " " + candList.toString());
        // base case
        if (n == 0) {
            if (total == t) {
                //System.out.println("*** " + candList.toString());
                combList.add(candList);
            }
            
            return;
        }
        if (total > t) return;

        // iterate including self
        for (int j = i; j < cand.length; ++j) {
            List<Integer> newCandList = new ArrayList<>();
            newCandList.addAll(candList);
            newCandList.add(cand[j]);
            createComb(j, n-1, total+cand[j], newCandList);
        }

        return;
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        cand = candidates;
        t = target;
        combList = new ArrayList<>();
        List<List<Integer>> ansList = new ArrayList<>();

        // n: number of picked elements in a single combination (=unit)
        for (int n = 1; n < target; ++n) {
            for (int i = 0; i < candidates.length; ++i) {
                combList = new ArrayList<>(); // reset
                createComb(i, n-1, cand[i], new ArrayList<>(Arrays.asList(cand[i])));
                ansList.addAll(combList);
            }
        }
        
        return ansList;
    }
}

풀이 해설

WIP

메모

• 파이썬 itertools 쓰다가 자바로 넘어오니까 눈물난다 진짜