Leetcode 337) Combination Sum IV

09 Aug 2021 in Algorithms

• Leetcode 518) Coin Change 2 에서 얻은 confusion 을 이 문제를 통해 분석해보자..
• 순열과 조합중에 이건 순열이다.

내 답안

class Solution {
    public int combinationSum4(int[] nums, int target){
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int i =0;i<dp.length;i++){
            for(int j=0;j<nums.length;j++){
                int cur= i-nums[j];
                if(cur>=0){
                    dp[i] += dp[cur];
                }
            }
        }
        return dp[target];
    }
}

다른 답안

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 1; i < target + 1; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}

오답

• nums[i] 어레이가 정렬돼있을 것이라고 생각해서.. 근데 정렬 안되있음

  1. 정렬을 먼저 시키거나
  2. 아니면 break하지말거나.

  => Arrays.sort , 배열 크기에 따라 또 사용하는 소트매커니즘이 다르다.

  ​ https://javanitto.tistory.com/6

class Solution {
    public int combinationSum4(int[] nums, int target){
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int i =0;i<dp.length;i++){
            for(int j=0;j<nums.length;j++){
                int cur= i-nums[j];
                if(cur>=0){
                    dp[i] += dp[cur];
                }else{break;}
            }
        }
        return dp[target];
    }
}