Question

Question: Use backtracking algorithm design to write Java code to solve the subset problem: given a set of distinct integers, return all possible subsets. for example, input: new int[] {1,2,3}

output: [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]

Answer 1

/* Subsets.java */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Subsets {

public static List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> sets = new ArrayList<>(); // create result list
Arrays.sort(nums);
backtrack(sets, new ArrayList<>(), nums, 0, nums.length);
return sets;
}
/**
* Backtracking
* Time Complexity: O(n^2)
* Space Complexity: O(n^2)
*/
private static void backtrack(List<List<Integer>> sets, List<Integer> set, int[] nums, int start, int end) {
sets.add(new ArrayList<>(set)); // add subset each time inside sets list
for (int i = start; i < end; i++) {
set.add(nums[i]);
backtrack(sets, set, nums, i + 1, end);// find all subset
set.remove(set.size() - 1);// remove extra
}
}
  
public static void main(String[] args) {
int num[] = {1,2,3};
//System.out.println(subsets(num)); // can print directly [[],[1]..]
// or convert to array and print subsets
Object sets[] = subsets(num).toArray();
for (int i = 0; i < sets.length; i++) {
System.out.print(sets[i]);
if(i < sets.length-1){
System.out.print(",");
}
  
}
System.out.println("");
}
}

/* OUTPUT */

/* PLEASE UPVOTE */