首页 > 代码库 > 正整数划分的另一种解法 (纯递归)

正整数划分的另一种解法 (纯递归)

Step 1: 
n ==1 : return 1 
n == 2 : return  [1,1],[2]


Step 2:
for n > 2
a.arr.push(n)
b.arr.push([n-1,1])


c.1 get result of recursion(n-2)
c.2 combine n==2 & result => ret
c.3 remove duplicate record in ret


code :


var splitN = function f(n){
if(n == 1) return new Array("1");
else if(n == 2)return new Array("1,1","2");
else{
var tmp = new Array();
tmp.push(n);
tmp.push((n-1) + ",1");


var arr2 = new Array("1,1","2");
var r = f(n-2);


for(var i = 0;i < r.length ; i++){
tmp.push(arr2[0]+"," + r[i]);
tmp.push(arr2[1]+"," + r[i]);
}


//sort each
for(var i = 0;i < tmp.length; i++)tmp [i] = tmp[i].toString().split(‘,‘).sort().join(‘,‘);


//remove duplicate
var tmp2 = new Array();
for(var i = 0;i < tmp.length; i++){if(tmp2.indexOf(tmp[i]) < 0) tmp2.push(tmp[i]);}


return tmp2;
}


}


var ret = splitN(6);
console.log(ret);