PowerSum time out test case

Question

Please need your help, I got one failed test case due to time out if anyone can help me to improve the time taken by code to be executed. This problem is from HackerRank website if anyone needs more explanation I will refer the link of the problem in the comments below

from itertools import  combinations


def powerSum(X, N,n=1,poss=[]):
    if(n**N <= X):
        poss.append(n)
        n+=1
        rslt = powerSum(X,N,n,poss)
    else:
        tmp=[]
        for _ in range(len(poss)):
            oc=combinations(poss,_+1)
            for x in oc:
                ok = sum([num**N for num in x])
                if(ok == X):    
                    tmp.append(ok)
        return len(tmp)
    return rslt

this is the link for the problem :https://www.hackerrank.com/challenges/the-power-sum/problem — Flupper, Mar 10 '20 at 19:34
Unrelated to your time--out, but relevant if you call your function repeatedly with different test cases: [using an empty list as default parameter does not do what you think you do](https://stackoverflow.com/questions/366422/what-is-the-pythonic-way-to-avoid-default-parameters-that-are-empty-lists). — M Oehm, Mar 10 '20 at 19:37

mss · Answer 1 · 2020-03-10T20:25:44.967

I am not good in python, but I hope below java code can be easily understood, This is a indirectly a variation of subset sum problem which is a dynamic programming problem where you have to find no. of ways to get a given particular sum given an array of values,so basically before applying subset problem, I have made a list of number which can be used in making the required sum by stopping at that number whose kth power exceed the x because starting from that natural number, further natural number are going to have much larger kth power value so no need of keeping them in our list so break there then it is just a dynamic programming problem as mentioned above where our list has value of kth power of valid natural number and we have to find the different way to get the sum x using those kth power values.

below is the code for more clear understanding

import java.util.*;

public class Main {
    public static int find_it(int x , int n , List<Integer> a , int [][] dp){

        for(int i = 0; i < n; ++i){
            dp[i][0] = 1;
        }
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j <= x; ++j){       
                dp[i][j] += dp[i - 1][j];
                if(j - a.get(i - 1) >= 0){
                    dp[i][j] += dp[i - 1][j - a.get(i - 1)];
                }
            }
        }
        return dp[n][x];    
    }
    public static void main(String [] args){

        Scanner input = new Scanner(System.in);
        int x = input.nextInt() , k = input.nextInt();
        List<Integer> a = new ArrayList<>();
        for(int i = 1; ; ++i){
            double value = Math.pow(i , k);
            if(value > x){
                break;
            }
            a.add((int)value);
        }
        int n = a.size();
        int [][]dp = new int[n + 1][x + 1];
        int answer = find_it(x , n , a , dp);
        System.out.println(answer);
        input.close();
    }
}

PowerSum time out test case

1 Answers1