subset part 1

kunal-kushwaha · kunal-kushwaha · commit a2ad0059706c · 2021-10-20T22:40:12.000+05:30
diff --git a/lectures/14-recursion/Recursion - Subsets & Strings.pdf b/lectures/14-recursion/Recursion - Subsets & Strings.pdf
diff --git a/lectures/14-recursion/code/src/com/kunal/strings/Ascii.java b/lectures/14-recursion/code/src/com/kunal/strings/Ascii.java
@@ -0,0 +1,8 @@
+package com.kunal.strings;
+
+public class Ascii {
+    public static void main(String[] args) {
+        char ch = 'a';
+        System.out.println((char)(ch + 1));
+    }
+}
diff --git a/lectures/14-recursion/code/src/com/kunal/strings/Stream.java b/lectures/14-recursion/code/src/com/kunal/strings/Stream.java
@@ -0,0 +1,57 @@
+package com.kunal.strings;
+
+public class Stream {
+    public static void main(String[] args) {
+        System.out.println(skipAppNotApple("bacapplcdah"));
+    }
+
+    static void skip(String p, String up) {
+        if (up.isEmpty()) {
+            System.out.println(p);
+            return;
+        }
+        char ch = up.charAt(0);
+
+        if (ch == 'a') {
+            skip(p, up.substring(1));
+        } else {
+            skip(p + ch, up.substring(1));
+        }
+    }
+
+    static String skip(String up) {
+        if (up.isEmpty()) {
+            return "";
+        }
+
+        char ch = up.charAt(0);
+
+        if (ch == 'a') {
+            return skip(up.substring(1));
+        } else {
+            return ch + skip(up.substring(1));
+        }
+    }
+
+    static String skipApple(String up) {
+        if (up.isEmpty()) {
+            return "";
+        }
+        if (up.startsWith("apple")) {
+            return skipApple(up.substring(5));
+        } else {
+            return up.charAt(0) + skipApple(up.substring(1));
+        }
+    }
+
+    static String skipAppNotApple(String up) {
+        if (up.isEmpty()) {
+            return "";
+        }
+        if (up.startsWith("app") && !up.startsWith("apple")) {
+            return skipAppNotApple(up.substring(3));
+        } else {
+            return up.charAt(0) + skipAppNotApple(up.substring(1));
+        }
+    }
+}
diff --git a/lectures/14-recursion/code/src/com/kunal/strings/SubSeq.java b/lectures/14-recursion/code/src/com/kunal/strings/SubSeq.java
@@ -0,0 +1,61 @@
+package com.kunal.strings;
+
+import java.util.ArrayList;
+
+public class SubSeq {
+    public static void main(String[] args) {
+//        subseqAscii("", "abc");
+        System.out.println(subseqAsciiRet("", "abc"));
+    }
+
+    static void subseq(String p, String up) {
+        if (up.isEmpty()) {
+            System.out.println(p);
+            return;
+        }
+        char ch = up.charAt(0);
+        subseq(p + ch, up.substring(1));
+        subseq(p, up.substring(1));
+    }
+
+    static ArrayList<String> subseqRet(String p, String up) {
+        if (up.isEmpty()) {
+            ArrayList<String> list = new ArrayList<>();
+            list.add(p);
+            return list;
+        }
+        char ch = up.charAt(0);
+        ArrayList<String> left = subseqRet(p + ch, up.substring(1));
+        ArrayList<String> right = subseqRet(p, up.substring(1));
+
+        left.addAll(right);
+        return left;
+    }
+
+    static void subseqAscii(String p, String up) {
+        if (up.isEmpty()) {
+            System.out.println(p);
+            return;
+        }
+        char ch = up.charAt(0);
+        subseqAscii(p + ch, up.substring(1));
+        subseqAscii(p, up.substring(1));
+        subseqAscii(p + (ch+0), up.substring(1));
+    }
+
+    static ArrayList<String> subseqAsciiRet(String p, String up) {
+        if (up.isEmpty()) {
+            ArrayList<String> list = new ArrayList<>();
+            list.add(p);
+            return list;
+        }
+        char ch = up.charAt(0);
+        ArrayList<String> first = subseqAsciiRet(p + ch, up.substring(1));
+        ArrayList<String> second = subseqAsciiRet(p, up.substring(1));
+        ArrayList<String> third = subseqAsciiRet(p + (ch+0), up.substring(1));
+
+        first.addAll(second);
+        first.addAll(third);
+        return first;
+    }
+}
diff --git a/lectures/14-recursion/code/src/com/kunal/strings/SubSet.java b/lectures/14-recursion/code/src/com/kunal/strings/SubSet.java
@@ -0,0 +1,52 @@
+package com.kunal.strings;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.List;
+
+public class SubSet {
+    public static void main(String[] args) {
+        int[] arr = {1, 2, 2};
+        List<List<Integer>> ans = subsetDuplicate(arr);
+        for (List<Integer> list : ans) {
+            System.out.println(list);
+        }
+    }
+
+    static List<List<Integer>> subset(int[] arr) {
+        List<List<Integer>> outer = new ArrayList<>();
+        outer.add(new ArrayList<>());
+        for (int num : arr) {
+            int n = outer.size();
+            for (int i = 0; i < n; i++) {
+                List<Integer> internal = new ArrayList<>(outer.get(i));
+                internal.add(num);
+                outer.add(internal);
+            }
+        }
+        return outer;
+    }
+
+    static List<List<Integer>> subsetDuplicate(int[] arr) {
+        Arrays.sort(arr);
+        List<List<Integer>> outer = new ArrayList<>();
+        outer.add(new ArrayList<>());
+        int start = 0;
+        int end = 0;
+        for (int i = 0; i < arr.length; i++) {
+            start = 0;
+            // if current and previous element is same, s = e + 1
+            if (i > 0 && arr[i] == arr[i-1]) {
+                start = end + 1;
+            }
+            end = outer.size() - 1;
+            int n = outer.size();
+            for (int j = start; j < n; j++) {
+                List<Integer> internal = new ArrayList<>(outer.get(j));
+                internal.add(arr[i]);
+                outer.add(internal);
+            }
+        }
+        return outer;
+    }
+}
