Leetcode 216) Combination Sum III

29 Jul 2021 in Algorithms

내 답안

• 그림 그려서 생각해보기

class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        int check =0;
        for(int i =1;i<k+1;i++){
            check +=i;
        }
        //입밴하기
        if(check > n){
            return res;
        }
        //n에 남은 숫자 넣기?
        List<Integer> cur = new ArrayList<Integer>();
        bt(1,k,n,cur);
        return res;
    }

    public void bt(int ind , int left , int n, List<Integer> cur){
        if(n==0 && left==0){
            res.add(cur);
            return;}
        //몇자리 남았는데 left가 0이된 것, 여기서 걸러진다. 
        if(n<=0){
            return;}

        if(left==0){
            //없애버려야함...? 이렇게 하면 어차피 더이상 안 내려가니까 ㄱㅊ을거같은데?
            return;
        }

        for(int i =ind ; i<10;i++){
            List<Integer> tmp = new ArrayList<>(cur);
            tmp.add(i);
            if(n-i>=0){
                //여기서 중복 안 된 줄 알았는데? 아닌갑다?
                bt(i+1, left-1,n-i,tmp);
            }
        }
    }
}

다른 답안

class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {

        List<List<Integer>> result = new ArrayList<>();
        int[] candidates = new int[]{1,2,3,4,5,6,7,8,9};
        dfs(candidates, k, n, 0, new ArrayList<>(), result);

        return result;
    }

    private void dfs(int[] candidates, int k , int remaining, int start, List<Integer> temp, List<List<Integer>> res){
        if(temp.size() == k && remaining == 0){
            //we found k number to sum to n 
            res.add(new ArrayList<>(temp));
            return;
        }

        for(int i=start; i<candidates.length; i++){
            if(remaining-candidates[i]<0) break;
            temp.add(candidates[i]);
            dfs(candidates, k, remaining-candidates[i], i+1, temp, res);
            temp.remove(temp.size()-1);
        }
    }
}

오답

• bt(ind+1 , left-1, n-i,tmp) 가 아니라 bt(i+1, left-1,n-i,tmp)다.

for(int i =ind ; i<10;i++){
    List<Integer> tmp = new ArrayList<>(cur);
    tmp.add(i);
    if(n-i>=0){
        //여기서 중복 안 된 줄 알았는데? 아닌갑다?
        bt(ind+1, left-1,n-i,tmp);
    }
}