Given a number T, print out all possible ways to get to T.


  • 1
    J

    Given a number T, print out all possible ways to get to T.

    For example,

    T = 5
    1 + 1 + 1 + 1
    2 + 1 + 1 + 1
    3 + 1 + 1
    2 + 2 + 1
    4 + 1
    3 + 2
    

    note that 3 + 2 is same as 2 + 3, so you don't have to print both cases

    What is the time complexity? Brute force is not allowed.


  • 0
    D

    No codes, just some ideas.
    First, there is a DP way.
    let Arr[x][y] means that the sum is X and the maximum added number is less than or equal to y.
    What we want is Arr[T][T]
    For initial, Arr[x][1] = 1...1 (1<= x <= T), Arr[0][0] = null and Arr[X][0] = error (X != 0)
    then Arr[X][Y] = sumWayOf( Arr[X- Y*i][Y-1]) ( 1<=i <= floor(X/Y) )
    To save the data. vector<vector<int>> Arr[T+1][T+1];

    also, it can be easily changed into a memorized dfs way.


Log in to reply
 

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