Find m numbers that sum to n in a sequence

user_912744 0
Viewed 117

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?

recursion algorithm javascript
3 Answers

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);
user_29796170 
const res = allCombinations(2, 5);

const unique = res.reduce((acc, curr) => {
   const exists = acc.some(item => item.sort().toString() === curr.sort().toString());

   return exists ? acc : [...acc, curr]; 
}, []);
user_139818860

I would recommend generators for this kind of problem -

  1. find solutions from 1..n
  2. of size m
  3. where q is the target sum, initialised to n

function* solve(n, m, q = n)
{ if (m == 0 && q == 0)
    yield []
  else if (n == 0 || q < 0)
    return
  else
  { for (const s of solve(n - 1, m - 1, q - n))
      yield [...s, n]
    yield *solve(n - 1, m, q)
  }
}

for (const p of solve(5, 2))
  console.log(p)

// [1,4]
// [2,3]

We can collapse the for loop above by using another default argument for the solution, s -

function* solve(n, m, q = n, s = [])             // s = []
{ if (m == 0 && q == 0)
    yield s
  else if (n == 0 || q < 0)
    return
  else
  { yield *solve(n - 1, m - 1, q - n, [n, ...s]) // update s
    yield *solve(n - 1, m, q, s)                 // pass s
  }
}

for (const p of solve(5, 2))
  console.log(p)

// [1,4]
// [2,3]

And we can collapse the if statements using early return -

function* solve(n, m, q = n, s = [])
{ if (m == 0 && q == 0) return yield s  // <-
  if (n == 0 || q < 0) return
  yield *solve(n - 1, m - 1, q - n, [n, ...s])
  yield *solve(n - 1, m, q, s)
}

console.log(JSON.stringify(Array.from(solve(5,2))))
// [[1,4],[2,3]]

console.log(JSON.stringify(Array.from(solve(9,3))))
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(Array.from(solve(27,6))))
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

If you don't like the extra parameters on solve, we can use an inner loop -

function solve(n, m)
{ function* loop(n, m, q, s)                   // "helper"
  { if (m == 0 && q == 0) return yield s
    if (n == 0 || q < 0) return
    yield *loop(n - 1, m - 1, q - n, [n, ...s])
    yield *loop(n - 1, m, q, s)
  }
  return loop(n, m, n, [])                     // n, m, q = n, s = []
}

console.log(JSON.stringify(Array.from(solve(5,2))))
// [[1,4],[2,3]]

console.log(JSON.stringify(Array.from(solve(9,3))))
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(Array.from(solve(27,6))))
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

If you don't like that it exposes the generator, you can return all results using Array.from -

function solve(n, m)
{ function* loop(n, m, q, s)
  { if (m == 0 && q == 0) return yield s
    if (n == 0 || q < 0) return
    yield *loop(n - 1, m - 1, q - n, [n, ...s])
    yield *loop(n - 1, m, q, s)
  }
  return Array.from(loop(n, m, n, []))   // Array.from
}

console.log(JSON.stringify(solve(5,2)))  // solve now returns array
// [[1,4],[2,3]]

console.log(JSON.stringify(solve(9,3)))  // <-
// [[1,2,6],[1,3,5],[2,3,4]]

console.log(JSON.stringify(solve(27,6))) // <-
// [[1,2,3,4,5,12],[1,2,3,4,6,11],[1,2,3,4,7,10],[1,2,3,5,6,10],[1,2,3,4,8,9],[1,2,3,5,7,9],[1,2,4,5,6,9],[1,2,3,6,7,8],[1,2,4,5,7,8],[1,3,4,5,6,8],[2,3,4,5,6,7]]

Mix and match any of these techniques to your heart's content!

user_6331830
Related