Repository: TheAlgorithms/Java
Pull request #5181 (2024-05-26 17:23:55)

refactor: redesign `ArrayCombination`
Related to #5164.

<!--
Thank you for your contribution!
In order to reduce the number of notifications sent to the maintainers, please:
- create your PR as draft, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/about-pull-requests#draft-pull-requests,
- make sure that all of the CI checks pass,
- mark your PR as ready for review, cf. https://docs.github.com/en/pull-requests/collaborating-with-pull-requests/proposing-changes-to-your-work-with-pull-requests/changing-the-stage-of-a-pull-request#marking-a-pull-request-as-ready-for-review
-->

<!-- For completed items, change [ ] to [x] -->

- [x] I have read [CONTRIBUTING.md](https://github.com/TheAlgorithms/Java/blob/master/CONTRIBUTING.md).
- [x] This pull request is all my own work -- I have not plagiarized it.
- [x] All filenames are in PascalCase.
- [x] All functions and variable names follow Java naming conventions.
- [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
- [x] All new code is formatted with `clang-format -i --style=file path/to/your/file.java`

codecov-commenter: ## [Codecov](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5181?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) Report
Attention: Patch coverage is `91.66667%` with `1 lines` in your changes are missing coverage. Please review.
> Project coverage is 38.61%. Comparing base [(`37c2a96`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/37c2a96fe2248ac554c2e474e71a6fbf78d2369a?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) to head [(`c848bab`)](https://app.codecov.io/gh/TheAlgorithms/Java/commit/c848babd226e9a182608165c771be44ad145aecc?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

| [Files](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5181?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) | Patch % | Lines |
|---|---|---|
| [...m/thealgorithms/backtracking/ArrayCombination.java](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5181?src=pr&el=tree&filepath=src%2Fmain%2Fjava%2Fcom%2Fthealgorithms%2Fbacktracking%2FArrayCombination.java&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms#diff-c3JjL21haW4vamF2YS9jb20vdGhlYWxnb3JpdGhtcy9iYWNrdHJhY2tpbmcvQXJyYXlDb21iaW5hdGlvbi5qYXZh) | 91.66% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5181?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff              @@
##             master    #5181      +/-   ##
============================================
+ Coverage     38.60%   38.61%   +0.01%     
- Complexity     2379     2380       +1     
============================================
  Files           516      516              
  Lines         15396    15402       +6     
  Branches       2957     2957              
============================================
+ Hits           5944     5948       +4     
  Misses         9167     9167              
- Partials        285      287       +2     
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/TheAlgorithms/Java/pull/5181?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=TheAlgorithms).

github-actions[bot]: This pull request has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contribution!

Patch:
diff --git a/src/main/java/com/thealgorithms/backtracking/ArrayCombination.java b/src/main/java/com/thealgorithms/backtracking/ArrayCombination.java
index a0b886e6..a064decc 100644
--- a/src/main/java/com/thealgorithms/backtracking/ArrayCombination.java
+++ b/src/main/java/com/thealgorithms/backtracking/ArrayCombination.java
@@ -1,32 +1,42 @@
 package com.thealgorithms.backtracking;
 
+import java.util.ArrayList;
 import java.util.List;
-import java.util.TreeSet;
 
 /**
- * Finds all permutations of 1...n of length k
- * @author TheClerici (<a href="https://github.com/TheClerici">git-TheClerici</a>)
+ * Finds all combinations of 0...n-1 of length k
  */
 public final class ArrayCombination {
     private ArrayCombination() {
     }
-    private static int length;
 
     /**
-     * Find all combinations of 1..n by creating an array and using backtracking in Combination.java
-     * @param n max value of the array.
-     * @param k length of combination
-     * @return a list of all combinations of length k. If k == 0, return null.
+     * Finds all combinations of length k of 0..n-1 using backtracking.
+     *
+     * @param n Number of the elements.
+     * @param k Length of the combination.
+     * @return A list of all combinations of length k.
      */
-    public static List<TreeSet<Integer>> combination(int n, int k) {
-        if (n <= 0) {
-            return null;
+    public static List<List<Integer>> combination(int n, int k) {
+        if (n < 0 || k < 0 || k > n) {
+            throw new IllegalArgumentException("Wrong input.");
         }
-        length = k;
-        Integer[] arr = new Integer[n];
-        for (int i = 1; i <= n; i++) {
-            arr[i - 1] = i;
+
+        List<List<Integer>> combinations = new ArrayList<>();
+        combine(combinations, new ArrayList<>(), 0, n, k);
+        return combinations;
+    }
+
+    private static void combine(List<List<Integer>> combinations, List<Integer> current, int start, int n, int k) {
+        if (current.size() == k) { // Base case: combination found
+            combinations.add(new ArrayList<>(current)); // Copy to avoid modification
+            return;
+        }
+
+        for (int i = start; i < n; i++) {
+            current.add(i);
+            combine(combinations, current, i + 1, n, k);
+            current.removeLast(); // Backtrack
         }
-        return Combination.combination(arr, length);
     }
 }


Test patch:
diff --git a/src/test/java/com/thealgorithms/backtracking/ArrayCombinationTest.java b/src/test/java/com/thealgorithms/backtracking/ArrayCombinationTest.java
index 23fa5d54..a4ff7fe8 100644
--- a/src/test/java/com/thealgorithms/backtracking/ArrayCombinationTest.java
+++ b/src/test/java/com/thealgorithms/backtracking/ArrayCombinationTest.java
@@ -1,51 +1,36 @@
 package com.thealgorithms.backtracking;
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
-import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertThrows;
 
+import com.thealgorithms.maths.BinomialCoefficient;
+import java.util.ArrayList;
 import java.util.List;
-import java.util.TreeSet;
-import org.junit.jupiter.api.Test;
+import java.util.stream.Stream;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.Arguments;
+import org.junit.jupiter.params.provider.MethodSource;
 
 public class ArrayCombinationTest {
-
-    @Test
-    void testNBeingZeroOrLess() {
-        List<TreeSet<Integer>> zeroResult = ArrayCombination.combination(0, 1);
-        List<TreeSet<Integer>> negativeResult = ArrayCombination.combination(-1, 1);
-        assertNull(zeroResult);
-        assertNull(negativeResult);
-    }
-
-    @Test
-    void testNoLengthElement() {
-        List<TreeSet<Integer>> result = ArrayCombination.combination(2, 0);
-        assertNull(result);
+    @ParameterizedTest
+    @MethodSource("regularInputs")
+    void testCombination(int n, int k, List<List<Integer>> expected) {
+        assertEquals(expected.size(), BinomialCoefficient.binomialCoefficient(n, k));
+        assertEquals(expected, ArrayCombination.combination(n, k));
     }
 
-    @Test
-    void testLengthOne() {
-        List<TreeSet<Integer>> result = ArrayCombination.combination(2, 1);
-        assert result != null;
-        assertEquals(1, result.get(0).iterator().next());
-        assertEquals(2, result.get(1).iterator().next());
+    @ParameterizedTest
+    @MethodSource("wrongInputs")
+    void testCombinationThrows(int n, int k) {
+        assertThrows(IllegalArgumentException.class, () -> ArrayCombination.combination(n, k));
     }
 
-    @Test
-    void testLengthTwo() {
-        List<TreeSet<Integer>> result = ArrayCombination.combination(2, 2);
-        assert result != null;
-        Integer[] arr = result.get(0).toArray(new Integer[2]);
-        assertEquals(1, arr[0]);
-        assertEquals(2, arr[1]);
+    private static Stream<Arguments> regularInputs() {
+        return Stream.of(Arguments.of(0, 0, List.of(new ArrayList<Integer>())), Arguments.of(1, 0, List.of(new ArrayList<Integer>())), Arguments.of(1, 1, List.of(List.of(0))), Arguments.of(3, 0, List.of(new ArrayList<Integer>())), Arguments.of(3, 1, List.of(List.of(0), List.of(1), List.of(2))),
+            Arguments.of(4, 2, List.of(List.of(0, 1), List.of(0, 2), List.of(0, 3), List.of(1, 2), List.of(1, 3), List.of(2, 3))));
     }
 
-    @Test
-    void testLengthFive() {
-        List<TreeSet<Integer>> result = ArrayCombination.combination(10, 5);
-        assert result != null;
-        Integer[] arr = result.get(0).toArray(new Integer[5]);
-        assertEquals(1, arr[0]);
-        assertEquals(5, arr[4]);
+    private static Stream<Arguments> wrongInputs() {
+        return Stream.of(Arguments.of(-1, 0), Arguments.of(0, -1), Arguments.of(2, 100));
     }
 }