For the same problem, different sequence of same numbers regarded as one combination.


  • 0
    S

    For the same problem, different sequence of same numbers regarded as one combination.

    For example, [1,2,3] target =4;

    different combinations are {
    1,1,1,1
    1,2,1
    2,2
    1,3
    }

    So the output should be 4.

    Is any dp solution for this question?


  • 0
    S

    I don't want the backtracking solution which output all combinations(same as Combination Sum problem), what I need is just the number of combinations.


  • 0
    S

    I am new to backpack problem. I tried to develop below code and verified by several simple tcs.
    Please help me to figure it out right or not. Also, if right, why just simply switch the outer-inner loop then we can get the results where order doesn't matter?

    ‘’‘
    public int makeChange3(int[] nums, int target){
    if(target==0) return 1;
    int[] dp=new int[target+1];
    dp[0]=1;

    for(int num : nums){
        for(int i=1; i<=target; i++){
            if(i>=num) dp[i]+=dp[i-num];
        }
    }
    return dp[target];
    

    }
    ''''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.