# How to find average time complexity of backtracking algorithm?

Problem is to decide if it is possible to partition a given array nums into k partitions. I've written a brute force backtracking algorithm. How do we analyse this algorithm to calculate average runtime (average over all possible inputs -input may be such that it ends up "back-tracking" multiple times or possibly none). I want to perform a rigorous analysis. Defition of the backtracking procedure, which is called from main() with arguments CanPartK(0,nums,visited,k,0,SUM) and visited[]=FALSE , is as follows:

 bool CanPartK(int start, vector<int>& nums, vector<bool>& visited, int k, int curr_sum,  const int& SUM)
{
// k*SUM = sum of elements of nums[]

if(k==0) return true;
if(curr_sum==SUM) return CanPartK(0, nums, visited, k-1, 0, SUM);

for(int i=start; i<nums.size(); i++)
{
if(!visited[i] && curr_sum+nums[i]<=SUM)
{
visited[i]=true;
if(!CanPartK(i+1, nums, visited, k, curr_sum+nums[i], SUM))
visited[i]=false;
else
return true;
}
}

return false;
}