.leetcode(39. Combination Sum)

문제

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

문제 풀기 전

1. recursion으로 풀면되겠다.
2. Group Anagrams 풀었던 걸 이용했다. 여기도 역시 중복을 하나로 체크해야하는데 그때 알파벳키를 만들었던것처럼 키를 만들어 유일값을 체크하면 되겠다 싶었다.

직접 푼 풀이

소요시간: 24분(20:12 ~ 20:36)

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Set<String> checkBox = new HashSet<String>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        doCombinationSum(candidates, target, new ArrayList<>());

        return result;
    }

    private void doCombinationSum(int[] candidates, int target, List<Integer> sub) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
            if (isNew(candidates, sub)) {
                List<Integer> temp = sub.stream()
                    .map(index -> candidates[index]).collect(Collectors.toList());
                result.add(temp);
            }
            return;
        } 

        for (int i=0; i<candidates.length; i++) {
            sub.add(i);
            doCombinationSum(candidates, target-candidates[i], sub);    
            sub.remove(sub.size()-1);
        }
    }

    private boolean isNew(int[] candidates, List<Integer> sub) {
        int[] keys = new int[candidates.length];
        for (int i=0; i<sub.size(); i++) {
            keys[sub.get(i)]++;
        }

        StringBuilder builder = new StringBuilder();
        for (int i=0; i<keys.length; i++) {
            builder.append(keys[i]).append(".");
        }
        String key = builder.toString();

        if (checkBox.contains(key)) {
            return false;
        }

        checkBox.add(key);
        return true;
    }
}

느낀점

1. 풀고나서 본건 느린 속도였다. 좀 더 빠르게 푸는 방법이 있을까.
2. 생각해보니 start만 정해도 isNew를 체크할 필요가 없다.
3. 솔루션도 backtrack으로 풀이가 되었다.
4. dp로 풀기를 시도 했으나 결국에는 못했다.

솔루션 공부 후 추가로 푼 풀이

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Set<String> checkBox = new HashSet<String>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        doCombinationSum(candidates, target, new ArrayList<>(), 0);

        return result;
    }

    private void doCombinationSum(int[] candidates, int target, List<Integer> sub, int start) {
        if (target < 0) {
            return;
        }

        if (target == 0) {
                List<Integer> temp = sub.stream()
                    .map(index -> candidates[index]).collect(Collectors.toList());
                result.add(temp);
            return;
        } 

        for (int i=start; i<candidates.length; i++) {
            sub.add(i);
            doCombinationSum(candidates, target-candidates[i], sub, i);    
            sub.remove(sub.size()-1);
        }
    }

}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)