In this article, we will learn to resolve the Find All Subsets problem in Java by using a backtracking algorithm

Problem

Given an array a, find all its subsets

Example

Array [1, 2, 3] will have the following subsets

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

Backtracking Approach

import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.List;

public class BackTracking_FindAllSubsets {  
    List<LinkedList<Integer>> result = new ArrayList<>();

    void printSubsets() {
        for (LinkedList<Integer> subset : result) {
            System.out.println(String.valueOf(subset));
        }
    }

    void enumerate(int[] a, int startIndex, LinkedList<Integer> currentSubset) {
        result.add(new LinkedList<>(currentSubset));

        for (int i = startIndex; i < a.length; i++) {
            currentSubset.addLast(a[i]);
            enumerate(a, i + 1, currentSubset);
            currentSubset.removeLast(); // backtracking
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 3};
        BackTracking_FindAllSubsets findAllSubsets = new BackTracking_FindAllSubsets();
        findAllSubsets.enumerate(a, 0, new LinkedList<>());
        findAllSubsets.printSubsets();
    }
}
Algorithm