Backtracking: Generate combination and permutation for a given array

This post provides a simple backtracking solution for computing permutation and combination of a given array.

For more information about permutation/combination see this post on math is fun.

Summary:

• If the order doesn't matter, it is a Combination.
• If the order does matter it is a Permutation.

Do not consider this approach for your production code, this should only be used for understanding backtracking as a means to compute combination. The complexity of this algorithm is factorial.

Algorithm: 

# Get input array.

# Create output array of the size equal to input array.

# Keep a pointer loc starting from 0 to size of input array -1

# for each location

# add all possible values from input array

# if location reaches the end, print the array, and return

The following code sample should be easy to follow:

package com.example;

public class PermutationBT {

 static char[] input = { 'a', 'b', 'c' };
 static char[] output = { '0', '0', '0' };

 public static void main(String[] args) {
  permute(0);
 }

 static boolean contains(char[] arr, char e) {
  for (int i = 0; i < arr.length; i++) {
   if (arr[i] == e)
    return true;
  }
  return false;
 }

 static void permute(int loc) {

  if (loc == input.length) {
   System.out.println(output);
   return;
  }

  for (int i = 0; i < input.length; i++) {
   char e = input[i];
   if (contains(output, e)) // #1
    continue; // #2
   output[loc] = e;
   permute(loc + 1);
  }
  output[loc] = 0;
 }

}

This prints the permutation by default. If you want to change to code to combination, comment lines #1 and #2.