Cleanup combination and combination test (TheAlgorithms#5902)

lorduke22 · web-flow · commit e6f70634a48b · 2024-10-26T18:39:23.000Z
diff --git a/src/main/java/com/thealgorithms/backtracking/Combination.java b/src/main/java/com/thealgorithms/backtracking/Combination.java
@@ -1,6 +1,7 @@
 package com.thealgorithms.backtracking;
 
 import java.util.Arrays;
+import java.util.Collections;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.TreeSet;
@@ -13,8 +14,6 @@ public final class Combination {
     private Combination() {
     }
 
-    private static int length;
-
     /**
      * Find all combinations of given array using backtracking
      * @param arr the array.
@@ -23,39 +22,45 @@ private Combination() {
      * @return a list of all combinations of length n. If n == 0, return null.
      */
     public static <T> List<TreeSet<T>> combination(T[] arr, int n) {
+        if (n < 0) {
+            throw new IllegalArgumentException("The combination length cannot be negative.");
+        }
+
         if (n == 0) {
-            return null;
+            return Collections.emptyList();
         }
-        length = n;
         T[] array = arr.clone();
         Arrays.sort(array);
+
         List<TreeSet<T>> result = new LinkedList<>();
-        backtracking(array, 0, new TreeSet<T>(), result);
+        backtracking(array, n, 0, new TreeSet<T>(), result);
         return result;
     }
 
     /**
      * Backtrack all possible combinations of a given array
      * @param arr the array.
+     * @param n length of the combination
      * @param index the starting index.
      * @param currSet set that tracks current combination
      * @param result the list contains all combination.
      * @param <T> the type of elements in the array.
      */
-    private static <T> void backtracking(T[] arr, int index, TreeSet<T> currSet, List<TreeSet<T>> result) {
-        if (index + length - currSet.size() > arr.length) {
+    private static <T> void backtracking(T[] arr, int n, int index, TreeSet<T> currSet, List<TreeSet<T>> result) {
+        if (index + n - currSet.size() > arr.length) {
             return;
         }
-        if (length - 1 == currSet.size()) {
+        if (currSet.size() == n - 1) {
             for (int i = index; i < arr.length; i++) {
                 currSet.add(arr[i]);
-                result.add((TreeSet<T>) currSet.clone());
+                result.add(new TreeSet<>(currSet));
                 currSet.remove(arr[i]);
             }
+            return;
         }
         for (int i = index; i < arr.length; i++) {
             currSet.add(arr[i]);
-            backtracking(arr, i + 1, currSet, result);
+            backtracking(arr, n, i + 1, currSet, result);
             currSet.remove(arr[i]);
         }
     }
diff --git a/src/test/java/com/thealgorithms/backtracking/CombinationTest.java b/src/test/java/com/thealgorithms/backtracking/CombinationTest.java
@@ -1,17 +1,28 @@
 package com.thealgorithms.backtracking;
 
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNotNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
 import static org.junit.jupiter.api.Assertions.assertTrue;
 
 import java.util.List;
+import java.util.Set;
 import java.util.TreeSet;
 import org.junit.jupiter.api.Test;
 
 public class CombinationTest {
 
+    @Test
+    void testNegativeElement() {
+        Integer[] array = {1, 2};
+        assertThrows(IllegalArgumentException.class, () -> { Combination.combination(array, -1); });
+    }
+
     @Test
     void testNoElement() {
         List<TreeSet<Integer>> result = Combination.combination(new Integer[] {1, 2}, 0);
-        assertTrue(result == null);
+        assertNotNull(result);
+        assertEquals(0, result.size());
     }
 
     @Test
@@ -28,4 +39,13 @@ void testLengthTwo() {
         assertTrue(arr[0] == 1);
         assertTrue(arr[1] == 2);
     }
+
+    @Test
+    void testCombinationsWithStrings() {
+        List<TreeSet<String>> result = Combination.combination(new String[] {"a", "b", "c"}, 2);
+        assertEquals(3, result.size());
+        assertTrue(result.contains(new TreeSet<>(Set.of("a", "b"))));
+        assertTrue(result.contains(new TreeSet<>(Set.of("a", "c"))));
+        assertTrue(result.contains(new TreeSet<>(Set.of("b", "c"))));
+    }
 }
