feat: add recursion subsets (#5503)

Tuhinm2002 · web-flow · commit 013d122e7dcb · 2024-10-02T18:51:23.000Z
diff --git a/src/main/java/com/thealgorithms/Recursion/GenerateSubsets.java b/src/main/java/com/thealgorithms/Recursion/GenerateSubsets.java
@@ -0,0 +1,36 @@
+package com.thealgorithms.Recursion;
+
+// program to find power set of a string
+
+import java.util.ArrayList;
+import java.util.List;
+
+public final class GenerateSubsets {
+
+    private GenerateSubsets() {
+        throw new UnsupportedOperationException("Utility class");
+    }
+
+    public static List<String> subsetRecursion(String str) {
+        return doRecursion("", str);
+    }
+
+    private static List<String> doRecursion(String p, String up) {
+        if (up.isEmpty()) {
+            List<String> list = new ArrayList<>();
+            list.add(p);
+            return list;
+        }
+
+        // Taking the character
+        char ch = up.charAt(0);
+        // Adding the character in the recursion
+        List<String> left = doRecursion(p + ch, up.substring(1));
+        // Not adding the character in the recursion
+        List<String> right = doRecursion(p, up.substring(1));
+
+        left.addAll(right);
+
+        return left;
+    }
+}
diff --git a/src/test/java/com/thealgorithms/Recursion/GenerateSubsetsTest.java b/src/test/java/com/thealgorithms/Recursion/GenerateSubsetsTest.java
@@ -0,0 +1,36 @@
+package com.thealgorithms.Recursion;
+
+import static org.junit.jupiter.api.Assertions.assertArrayEquals;
+
+import java.util.List;
+import org.junit.jupiter.api.Test;
+
+public final class GenerateSubsetsTest {
+
+    @Test
+    void subsetRecursionTestOne() {
+        String str = "abc";
+        String[] expected = new String[] {"abc", "ab", "ac", "a", "bc", "b", "c", ""};
+
+        List<String> ans = GenerateSubsets.subsetRecursion(str);
+        assertArrayEquals(ans.toArray(), expected);
+    }
+
+    @Test
+    void subsetRecursionTestTwo() {
+        String str = "cbf";
+        String[] expected = new String[] {"cbf", "cb", "cf", "c", "bf", "b", "f", ""};
+
+        List<String> ans = GenerateSubsets.subsetRecursion(str);
+        assertArrayEquals(ans.toArray(), expected);
+    }
+
+    @Test
+    void subsetRecursionTestThree() {
+        String str = "aba";
+        String[] expected = new String[] {"aba", "ab", "aa", "a", "ba", "b", "a", ""};
+
+        List<String> ans = GenerateSubsets.subsetRecursion(str);
+        assertArrayEquals(ans.toArray(), expected);
+    }
+}
