Last active
August 1, 2024 12:03
-
-
Save omidp/974bce6bdb8edbb4de9de907dba2c996 to your computer and use it in GitHub Desktop.
PowersetCombination with backtracking
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public List<List<Integer>> subsets(int[] nums) { | |
| List<List<Integer>> ans = new LinkedList<>(); | |
| backtrack(nums, 0, new LinkedList<>(), ans); | |
| return ans; | |
| } | |
| void backtrack(int[] nums, int i, List<Integer> cur, List<List<Integer>> ans){ | |
| ans.add(new ArrayList<>(cur)); | |
| for (int j = i; j<nums.length; j++){ | |
| cur.add(nums[j]); | |
| backtrack(nums, j + 1, cur, ans); | |
| cur.remove(cur.size() - 1); | |
| } | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.List; | |
| public class PowersetCombination { | |
| // Method to generate all k-combinations of a given set | |
| public static <T> List<List<T>> generateCombinations(List<T> set, int k) { | |
| List<List<T>> combinations = new ArrayList<>(); | |
| generateCombinations(set, k, 0, new ArrayList<>(), combinations); | |
| return combinations; | |
| } | |
| // Helper method for generateCombinations | |
| private static <T> void generateCombinations(List<T> set, int k, int start, List<T> current, List<List<T>> combinations) { | |
| if (current.size() == k) { | |
| combinations.add(new ArrayList<>(current)); | |
| return; | |
| } | |
| for (int i = start; i < set.size(); i++) { | |
| current.add(set.get(i)); | |
| generateCombinations(set, k, i + 1, current, combinations); | |
| current.remove(current.size() - 1); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| List<Integer> set = List.of(1, 2, 3); | |
| int k = 2; | |
| List<List<Integer>> combinations = generateCombinations(set, k); | |
| System.out.println("Combinations of size " + k + ": " + combinations); | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import java.util.ArrayList; | |
| import java.util.List; | |
| public class PowersetCombination { | |
| // Method to generate the powerset of a given set | |
| public static <T> List<List<T>> generatePowerset(List<T> set) { | |
| List<List<T>> powerset = new ArrayList<>(); | |
| // Start with the empty subset | |
| powerset.add(new ArrayList<>()); | |
| // Iterate over each element in the original set | |
| for (T element : set) { | |
| // Temporary list to store new subsets generated in this iteration | |
| List<List<T>> newSubsets = new ArrayList<>(); | |
| // For each existing subset, create a new subset that includes the current element | |
| for (List<T> subset : powerset) { | |
| List<T> newSubset = new ArrayList<>(subset); | |
| newSubset.add(element); | |
| newSubsets.add(newSubset); | |
| } | |
| // Add the newly created subsets to the powerset | |
| powerset.addAll(newSubsets); | |
| } | |
| return powerset; | |
| } | |
| public static void main(String[] args) { | |
| List<Integer> set = List.of(1, 2, 3); | |
| List<List<Integer>> powerset = generatePowerset(set); | |
| System.out.println("Powerset: " + powerset); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment