Problem
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
Example
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
JavaScript Code
function combine(n, k) { var result = []; //illegal case if (k > n) { return null; //if k==n } else if (k == n) { var temp = []; for (var i = 1; i <= n; i++) { temp.push(i); } result.push(temp); return result; //if k==1 } else if (k == 1) { for (var i = 1; i <= n; i++) { var temp = []; temp.push(i); result.push(temp); } return result; } //for normal cases, initialize a list with one element for (var i = 1; i <= n - k + 1; i++) { var temp = []; temp.push(i); result.push(temp); } return combineHelper(n, k, result); } function combineHelper(n, k, result) { var prevResult = result.slice(); if(result[0].length == k) return result; result = []; for (var j=0; j<prevResult.length; j++) { var one = prevResult[j]; for (var i = 1; i <= n; i++) { if (i > one[one.length - 1]) { var temp = one.slice(); temp.push(i); result.push(temp); } } } return combineHelper(n, k, result); }
Using Depth First Search
var result = []; function combine(n, k) { if (n <= 0 || n < k) return result; var item = []; dfs(n, k, 1, item); // because it need to begin from 1 } function dfs(n, k, start, item) { if (item.length == k) { result.push(item.slice()); return; } for (var i = start; i <= n; i++) { item.push(i); dfs(n, k, i + 1, item); item.pop(); } }
123betting thanks for the code It is very helpful to me. https://www.123betting.org/
ReplyDelete