import random
import unittest
from example import combinations_for_sum


class BacktrackingTests(unittest.TestCase):
    def test_edges_and_duplicates(self):
        self.assertEqual(combinations_for_sum([], 0), [[]])
        self.assertEqual(combinations_for_sum([], 2), [])
        self.assertEqual(combinations_for_sum([1, 1, 2, 3], 4), [[1, 1, 2], [1, 3]])
        with self.assertRaises(ValueError):
            combinations_for_sum([-1, 2], 1)

    def test_against_subsets(self):
        rng = random.Random(11)
        for _ in range(100):
            values = [rng.randint(1, 5) for _ in range(rng.randrange(8))]
            target = rng.randrange(14)
            expected = set()
            for mask in range(1 << len(values)):
                picked = [x for i, x in enumerate(values) if mask & (1 << i)]
                if sum(picked) == target:
                    expected.add(tuple(sorted(picked)))
            actual = combinations_for_sum(values, target)
            self.assertEqual({tuple(x) for x in actual}, expected)
            self.assertEqual(len(actual), len(expected))


if __name__ == '__main__':
    unittest.main()