Finding All the Subsets of a Set – Backtracking Problem

Given a set of distinct integers, S, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,3], a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

We use the backtracking method to solve this problem. Backtracking is the refinement method of Brute-Force method. Backtrack method means it finds the number of sub solutions and each may have number of sub divisions, and solution chosen for exactly one.

Backtracking method is a recursive method.

public class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    
    public List<List<Integer>> subsets(int[] S) {
        int[] A = new int[S.length];
        Arrays.sort(S);
        backTrack(A,0,S.length,S);
        return res;
    }
    
    public void processSolution(int[] A,int[] S){
        List<Integer> temp = new ArrayList<Integer>();
        for(int i=0; i<S.length; i++){
            if(A[i]==1){
                temp.add(S[i]);
            }
        }
        res.add(temp);
    }
    
    public void backTrack(int[] A, int k, int n, int[] S){
        if(k==n){
            processSolution(A,S);
        }else{
            for(int i=0; i<=1; i++){
                A[k]=i;
                backTrack(A,k+1,n,S);
            }
        }
    }
}