Finding all possible combinations - BFS

https://www.linkedin.com/pulse/finding-all-possible-combinations-bfs-kunal-saxena/ import java.util.*; /** * Finding all combinations from array of Numbers say {1,2,3,4} We want to make * combination of r numbers, So if r=3 then combinations will be {1,2,3}, * {1,3,2}, {2,3,1}..etc * * @author Kunal.Saxena * */ public class AllCombinationsFromNumbers { private final static List> combList = new ArrayList<>(); //list of list as result public static void findAllCombinations(int[] arr, int r) { // Queue for storing all paths Queue> paths = new LinkedList<>(); //store partial path // Initialize queue with array elements //e.g [1,2,3], starts with [1], [2], [3] for (int i : arr) { List list = new LinkedList<>(); list.add(i); paths.add(list); list = null; } while (!paths.isEmpty()) { // dequeue a path List path = paths.remove(); // Loop through all array elements for (int i : arr) { if (!path.contains(i)) { if (path.size() == r) { combList.add(path); continue; } List newPath = new LinkedList<>(path); newPath.add(i); paths.add(newPath); newPath = null; } } } } public static void main(String[] args) { // Input array and r int[] arr = { 1, 2, 3, 4 }; int r = 3; // Find all combinations of r elements findAllCombinations(arr, r); // print all combinations System.out.println("All possible combinations are :-"); for (List arrEle : combList) { System.out.println(arrEle); } } }