Given a sequence from 1 to n, I want to find all the unique subsequences of size m that sum up to n. The subsequences don't need to be contiguous. For example
if m = 2, n = 5
The possible unique subsequences of size 2 are {1,4} and {2,3}
So far I've been able to generate all the subsequences using recursion but my code is not returning only the unique subsequences, there are some duplicates in the result.
function allCombinations(m, n) {
if (m < 1) {
return [];
}
let helper = function(m, n, arr, result, index){
if (n < 0 || m < 0) {
return 0;
}
if (m === 0 && n === 0) {
result.push(arr.slice());
return 1;
}
for (let i = index; i <= n; i++){
arr.push(i);
helper(m - 1, n - i, arr, result, index + 1);
arr.pop();
}
}
let result = [];
helper(m, n, [], result, 0);
return result;
}
and when calling with
let res = allCombinations(2, 5);
the result is
[ [ 1, 4 ], [ 2, 3 ], [ 3, 2 ] ]
and as you can see {3,2} is a duplicate of {2,3}. How can I change my code so it returns only the unique sequences?
You can enforce that the next pick is greater than the current one by calling the recursive helper function with i instead of index:
for (let i = index; i <= n; i++){
arr.push(i);
helper(m - 1, n - i, arr, result, i + 1);
arr.pop();
}
This will yield unique sequences where the elements are sorted in ascending order. If you call it with just i, you allow duplicate picks.
Changing this will allow zero as pick unless you call the helper with index 1 from the wrapper function:
let result = [];
helper(m, n, [], result, 1);
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다