Skip to content

Instantly share code, notes, and snippets.

@omidp

omidp/PowersetCombination.java

Last active August 1, 2024 12:03
Show Gist options
  • Save omidp/974bce6bdb8edbb4de9de907dba2c996 to your computer and use it in GitHub Desktop.
Save omidp/974bce6bdb8edbb4de9de907dba2c996 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. omidp revised this gist Aug 1, 2024. 1 changed file with 16 additions and 0 deletions.
    16 changes: 16 additions & 0 deletions backtrack.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,16 @@
    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);
    }
    }
    }
  2. omidp revised this gist Jul 31, 2024. 1 changed file with 32 additions and 0 deletions.
    32 changes: 32 additions & 0 deletions powersetcombination2.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,32 @@
    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);
    }
    }
  3. omidp created this gist Jul 31, 2024.
    32 changes: 32 additions & 0 deletions PowersetCombination.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,32 @@
    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);
    }
    }