## Interview Question

Front-end Software Engineers**Country:**United States

This type of problem is typically known as Partition problem. The number of partitions of a number grows exponentially. I read somewhere that Its an NP-Complete problem. Here are few references that you can check to know more about it.

math.stackexchange.com/questions/217597/number-of-ways-to-write-n-as-a-sum-of-k-nonnegative-integers

en.wikipedia.org/wiki/Partition_%28number_theory%29#Intermediate_function

stackoverflow.com/questions/400794/generating-the-partitions-of-a-number#400810

Some of these links will provide you with the implementation in some lang. You can go through the math for wikipedia link.

```
function countSteps(n){
var counts = 0;
function partition(arr, last ,m){
var tempArr;
if(m > 1){
for(var i = last || 1; i <= m/2; i++){
tempArr = arr.slice(0);
if(m-i > i){
tempArr.push(i);
if(m-i > 1){
partition(tempArr.slice(0), i, m-i);
}
tempArr.push(m-i);
}else if(m-i == i){
tempArr.push(i);
tempArr.push(m-i);
}else{
return
}
}
}else{
tempArr = arr.slice(0);
tempArr.push(m);
}
if(tempArr){
counts += 1;
console.log(tempArr);
}
}
partition([], null, n);
return counts;
}
```

var all = [];

function findStep(n) {

if (n===1){

console.log(1);

} else {

_findIt(n, []);

}

all.sort();

var prev = [];

for(var i=0; i<all.length; i++){

var curr = all[i];

if (curr.join() == prev.join()){

all.splice(i,1);

i--;

} else {

prev = curr;

}

}

console.log(all);

console.log(all.length);

}

function getSum (arr){

return arr.reduce(function(a,b){

return a+b;

},0);

}

function _findIt(n, result){

var currentSum = getSum(result);

for(var i = 1; i <= n; i++){

var nextSum = currentSum + i;

if (nextSum === n){

result.push(i);

result.sort();

//console.log(result.join());

all.push(result);

return;

} else {

var newArray = result.slice(0);

newArray.push(i);

_findIt(n, newArray);

}

}

}

findStep(4)

I am not sure about the exact problem.

- Nitin Gupta January 28, 2014But from example it seems that you have to write an algorithm, with all permutation and combinations whose sum of digits is given number.