BackTrack.java

package com.shail;

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

public class BackTrack {

	// [1, 2, 3] => {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}
	// Ordering matters
	public List<List<Integer>> permute(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> result = new ArrayList<>();
		permuteHelper(nums, new ArrayList<>(), result, new boolean[nums.length]);
		return result;
	}

	private void permuteHelper(int[] a, List<Integer> curr, List<List<Integer>> result, boolean[] visited) {
		if(curr.size() == a.length){
			result.add(new ArrayList<>(curr));
			return;
		}

		// We start with i = 0 because the ordering matters.
		for(int i = 0; i < a.length; i++) {
			if(visited[i]) continue;
			if(i != 0 && a[i] == a[i-1] && visited[i]) continue;

			visited[i] = true;
			curr.add(a[i]);

			permuteHelper(a, curr, result, visited);

			curr.remove(curr.size()-1);
			visited[i] = false;
		}
	}

	//{1, 2, 3} => {}, {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, {3}
	// Ordering does not matter
	public List<List<Integer>> subsetsWithDup(int[] nums) {
		Arrays.sort(nums);
		List<List<Integer>> result = new ArrayList<>();
		subsetsHelper(nums, new ArrayList<>(), result, 0);
		return result;
	}

	private void subsetsHelper(int[] a, List<Integer> curr, List<List<Integer>> result, int start) {
		result.add(new ArrayList<>(curr));
		// We start with i = start because ordering does not matter
		for(int i = start; i < a.length; i++) {
			if(i != start && a[i] == a[i-1]) continue;
			curr.add(a[i]);
			subsetsHelper(a, curr, result, i + 1);
			curr.remove(curr.size()-1);
		}
	}

	// {1, 2, 3}, 2 => {1, 2}, {1, 3}, {2, 3}
	// Ordering does not matter
	private List<List<Integer>> combinationsWithDup(int[] nums, int k) {
		Arrays.sort(nums);
		List<List<Integer>> result = new ArrayList<>();
		combinationsHelper(nums, k, new ArrayList<>(), result, 0);
		return result;
	}

	private void combinationsHelper(int[] a, int k, List<Integer> curr, List<List<Integer>> result, int start) {
		if(curr.size() == k) {
			result.add(new ArrayList<>(curr));
			return;
		}

		// We start with i = start because ordering does not matter
		for(int i = start; i < a.length; i++) {
			if(i != start && a[i] == a[i-1]) continue;
			curr.add(a[i]);
			combinationsHelper(a, k, curr, result, i+1);
			curr.remove(curr.size()-1);
		}
	}

	public static void main(String[] args) {
		BackTrack bt = new BackTrack();
		int[] a = {1, 2, 3};
		System.out.println(bt.permute(a));
		System.out.println(bt.subsetsWithDup(a));
		System.out.println(bt.combinationsWithDup(a, 2));
	}
}