subset.java

public class Backtracking {
   
   ArrayList<ArrayList<Integer>> subsets;

    public Backtracking() {
        this.subsets = new ArrayList<ArrayList<Integer>>();
        this.subsets.add(new ArrayList<Integer>());
    }

    public ArrayList<ArrayList<Integer>> subsets(ArrayList<Integer> a) {

        Collections.sort(a);

        this.backtrackSubset(a, new ArrayList<Integer>(), 0);

        return this.subsets;
    }

    private void backtrackSubset(ArrayList<Integer> a, ArrayList<Integer> subSet, int k) {

        if (k == a.size()) {
            return;
        }

        for (int i = k; i < a.size(); i++) {
            ArrayList<Integer> subSetCopy  = this.deepCopy(subSet);
            subSetCopy.add(a.get(i));
            this.subsets.add(subSetCopy);
            backtrackSubset(a, subSetCopy, i + 1);
        }
    }


    private ArrayList<Integer> deepCopy(ArrayList<Integer> a) {
        ArrayList<Integer> b = new ArrayList<Integer>();

        for (Integer c:a) {
            b.add(c);
        }

        return b;
    }


}