Java/src/test/java/com/thealgorithms/recursion/CombinationSumTest.java at 59d8bebc93e737ed1ffdd9a3b0e735b46d6a30d3 · Tejasrahane/Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
package com.thealgorithms.recursion;
import static org.junit.jupiter.api.Assertions.*;
import java.util.Arrays;
import java.util.List;
import org.junit.jupiter.api.Test;
/**
 * Comprehensive test class for CombinationSum algorithm
 * Tests various scenarios including edge cases
 */
class CombinationSumTest {
    @Test
    void testBasicCase() {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertTrue(result.contains(Arrays.asList(2, 2, 3)));
        assertTrue(result.contains(Arrays.asList(7)));
        assertEquals(2, result.size());
    }
    @Test
    void testMultipleCombinations() {
        int[] candidates = {2, 3, 5};
        int target = 8;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertTrue(result.contains(Arrays.asList(2, 2, 2, 2)));
        assertTrue(result.contains(Arrays.asList(2, 3, 3)));
        assertTrue(result.contains(Arrays.asList(3, 5)));
        assertEquals(3, result.size());
    }
    @Test
    void testNoSolution() {
        int[] candidates = {2};
        int target = 1;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertTrue(result.isEmpty());
    }
    @Test
    void testSingleElement() {

        int[] candidates = {1};
        int target = 1;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertEquals(1, result.size());
        assertTrue(result.contains(Arrays.asList(1)));
    }
    @Test
    void testSingleElementRepeated() {

        int[] candidates = {2};
        int target = 8;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertEquals(1, result.size());
        assertTrue(result.contains(Arrays.asList(2, 2, 2, 2)));
    }
    @Test
    void testLargerNumbers() {

        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertFalse(result.isEmpty());
        // Verify all combinations sum to target
        for (List<Integer> combination : result) {
            int sum = combination.stream().mapToInt(Integer::intValue).sum();
            assertEquals(target, sum);
        }
    }
    @Test
    void testTargetZero() {

        int[] candidates = {1, 2, 3};
        int target = 0;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        // Should return empty list in the combination
        assertEquals(1, result.size());
        assertTrue(result.get(0).isEmpty());
    }
    @Test
    void testEmptyCandidates() {

        int[] candidates = {};
        int target = 5;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertTrue(result.isEmpty());
    }
    @Test
    void testLargeTarget() {
        int[] candidates = {3, 5, 8};
        int target = 11;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        assertTrue(result.contains(Arrays.asList(3, 3, 5)));
        assertTrue(result.contains(Arrays.asList(3, 8)));

        // Verify all combinations sum to target
        for (List<Integer> combination : result) {
            int sum = combination.stream().mapToInt(Integer::intValue).sum();
            assertEquals(target, sum);
        }
    }
    @Test
    void testAllCombinationsValid() {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        List<List<Integer>> result = CombinationSum.combinationSum(candidates, target);

        // Verify each combination sums to target
        for (List<Integer> combination : result) {
            int sum = 0;
            for (int num : combination) {
                sum += num;
            }
            assertEquals(target, sum, "Each combination should sum to target");
        }

        // Verify no duplicates in result
        assertEquals(result.size(), result.stream().distinct().count());
    }
}