Generate Unique Combinations

export function generateUniqueCombinations(ids: string[]): string[][][] {
  const results: string[][] = []

  function recurse(current: string[], remaining: string[]): void {
    results.push(current)
    for (let i = 0; i < remaining.length; i++) {
      recurse([...current, remaining[i]], remaining.slice(i + 1))
    }
  }

  const sortedIds = ids.sort()
  recurse([], sortedIds)

  return results
    .filter(isEmpty)
    .reduce<string[][]>((r, current) => removeDuplicates(r, current, sortedIds), [])
    .map(i => addUnusedIds(i, sortedIds))
}

const isEmpty = <T>(x: T[]) => x.length > 0

export function removeDuplicates(result: string[][], current: string[], sortedIds: string[]): string[][] {
  const unused = sortedIds.filter(id => !current.includes(id))
  const unusedHash = unused.join()
  const hasUnused = result.find(x => x.join() === unusedHash)
  return Boolean(hasUnused) ? result : [...result, current]
}

const addUnusedIds = (result: string[], ids: string[]): string[][] => {
  const unused = ids.filter(id => !result.includes(id))
  return unused.length === 0 ? [result] : [result, unused]
}

describe('Generate Unique Combinations', () => {
  test('Four items', () => {
    const items: string[] = ['abc', 'def', 'ghi', 'jkl']
    const results = generateUniqueCombinations(items)
    const expected = [
      [ [ 'abc' ], [ 'def', 'ghi', 'jkl' ] ],
      [ [ 'abc', 'def' ], [ 'ghi', 'jkl' ] ],
      [ [ 'abc', 'def', 'ghi' ], [ 'jkl' ] ],
      [ [ 'abc', 'def', 'ghi', 'jkl' ] ],
      [ [ 'abc', 'def', 'jkl' ], [ 'ghi' ] ],
      [ [ 'abc', 'ghi' ], [ 'def', 'jkl' ] ],
      [ [ 'abc', 'ghi', 'jkl' ], [ 'def' ] ],
      [ [ 'abc', 'jkl' ], [ 'def', 'ghi' ] ]
    ] 
    expect(results).toEqual(expected)
  })
})