Leetcode 39) Combination Sum

29 Jul 2021 in Algorithms

내 답안

• 큐에 담아서 하나씩 체크하는..
• candidates 정렬해서 놓은 후 진행.
• 그리고 마지막 원소보다 작은 원소를 선택하게 되면 중복이 나타나니까, 그러지 못하게..

class Solution {
    List<List<Integer>> res;

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

        //queue로 구현가능할 것 같다.
        Queue<List<Integer>> q = new LinkedList<>();

        //initialize로 모든 원소를 추가해준다.
        Arrays.sort(candidates);
        for(int i : candidates){
            if(i<target){
                q.add(Arrays.asList(i));
            }else if(i==target){
                res.add(Arrays.asList(i));
                break; // 정렬돼있으니까, 확신의 브레이크
            }               
        }

        //queue에 다 있을 때
        while(!q.isEmpty()){
            List<Integer> tmp =q.poll();
            int sum = 0;
            int last =0;
            for(int i : tmp){
                sum+=i;
                last = i;
            }
            //전 element보다 크거나 같은 수만 넣게해야지 중복이 안 날 듯. 

            for(int i :candidates){
                if(i<last){
                    continue;
                }

                if(sum + i < target){
                    //deepcopy 해 줌.
                    List<Integer> newlist = deepcopy(tmp);
                    newlist.add(i);
                    q.add(newlist);
                }else if (sum +i == target){
                    List<Integer> newlist = deepcopy(tmp);
                    newlist.add(i);
                    res.add(newlist);
                }
            }
        }
        return res;
    }
    private ArrayList<Integer> deepcopy(List<Integer> old){
        ArrayList<Integer> copy = new ArrayList<Integer>(old.size());
        for(Integer i : old){
            copy.add(new Integer(i));
        }
        return copy;
    }
}

다른 답안

• 여기선 target을 바꾼다!!! 타겟이 5이고, 이 어레이 합이 2면 target이 3이됨! 똑똑하네..
• target이 0보다 작다는 거는, 이미 초과했다는 것. 그러니 return.

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public void helper(int[] nums, int target, List<Integer> sofar,int start){
        if( target == 0){
            result.add(new ArrayList<>(sofar));
            return;
        }
        if(target <0){
            return;
        }
        for(int i = start; i<nums.length; i++){
            if(nums[i]<=target){
                sofar.add(nums[i]);
                helper(nums, target-nums[i],sofar,i);
                sofar.remove(sofar.size()-1);
            }
        }
        return;
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target){
        helper(candidates, target, new ArrayList<>(), 0);
        return result;
    }
}

주의

• 재귀할 때, 첫번째 콜이 어떻게 진행될 지 구체적으로 생각하기.

• arraylist deep copy 생각하기! 이런 식으로 해도 deep copy된다.

  List<Integer> newlist = new ArrayList<Integer>(tmp);
  

• 중복이 되면 안됨 (일케되면 중복)

  • for문 시작값도 arg로 정보준다.

  class Solution {
      List<List<Integer>> res=new ArrayList<List<Integer>>();
    
      public List<List<Integer>> combinationSum(int[] candidates, int target) {        
          List<Integer> l = new ArrayList<Integer>();
          bt(target,candidates,l);
          return res;
      }
    
      public void bt(int target, int[] candidates , List<Integer> l){
          if(target==0){
              List<Integer> a = new ArrayList<Integer>(l);
              res.add(a);
              return;
          }
    
          if(target<0){
              return;
          }
    
          for(int i =0;i<candidates.length;i++){
              List<Integer> a = new ArrayList<Integer>(l);
              a.add(candidates[i]);
              bt(target-candidates[i],candidates,a);
          }
          return;
      }
  }