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.

BFS: Breadth First Search for Trees/Graphs in Java

BFS is easy to understand if explained in Java, than C. The advantage being you can focus on the algorithm rather than the intricacies of the implementation.

Algorithm:

1. Initialize queue (q)
2. Push root node to queue
3. While queue not empty
4. Dequeue n
5. If n == required_node, return n;
6. foreach vertices v of n
7. if v is visited, continue
8. else enque v
9. return null; 

The algorithm might look quite vague. Just follow the code, it will be easy to understand.

Code: BFSDemo.java

package com.example;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

public class BFSDemo {

 // define node here
 static class Node {

  int value;
  boolean visited = false; // optional
  List vertices = new ArrayList<>();

  public Node(int value) {
   super();
   this.value = value;
  }

  public void addVertex(Node n) {
   vertices.add(n);
  }

  @Override
  public String toString() {
   return "Node [value=" + value + ", visited=" + visited
     + ", vertices=" + vertices + "]";
  }
 };

 public static Node find(Node root, int element) {
  // #1: Initialize queue (q)
  Queue q = new ConcurrentLinkedQueue<>(); // some queue
              // implementation
  // #2: Push root node to queue
  q.add(root);

  // #3: While queue not empty
  while (!q.isEmpty()) {

   // #:4 Dequeue n
   Node n = q.poll();
   // visit this node
   n.visited = true;

   // #5: If n == required_node, return n;
   if (n.value == element)
    return n;

   // #5: foreach vertices v of n
   for (Node v : n.vertices) {
    // #6: if v is visited, continue
    if (v.visited)
     continue;
    // #7: else enque v
    q.add(v);
   }
  }
  // #8: return null;
  return null; // cannot find element
 }

 public static void main(String[] args) {

  // create graph/tree
  Node n1 = new Node(1);
  Node n2 = new Node(2);
  Node n3 = new Node(3);
  Node n4 = new Node(4);
  Node n5 = new Node(5);

  // call traverse
  n1.addVertex(n2);
  n1.addVertex(n3);

  n3.addVertex(n4);
  n3.addVertex(n5);

  Node found = find(n1, 4);
  System.out.println(found); 
  // Node [value=4, visited=true, vertices=[]]
  
  found = find(n1, 7);
  System.out.println(found); 
  // null
 }
}

This logic is same for trees. The difference being: 

• Each node has only 2 children. 
• No need for visited flag in node.

Backtracking: Tug of War

Refer to the question at GFG:
http://www.geeksforgeeks.org/tug-of-war/

The solution given here is much easier to understand and its in Java.

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.

For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).

package com.example;

public class TugOfWar {

 static int[] a = { 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4 };
 static int n = a.length;
 static int minDiff = Integer.MAX_VALUE;
 static boolean[] solution = new boolean[n];
 static boolean[] selected = new boolean[n];

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

 // the solution is simple,

 // 1. in each iteration, either add or remove the current element from the selected array
 // 2. check if we have already selected the requried number of elements, in that case update solution
 // 3. check if have already reached the end of the array, in that case, simply return
 protected static void solve(int currentIndex) {

  // get size of selected
  int selectedSize = 0;
  for (int i = 0; i < n; i++)
   if (selected[i])
    selectedSize++;

  if (selectedSize == n / 2) {
   // check if diff < minDiff, update solution
   int diff = getDiff();
   if (diff < minDiff) {
    minDiff = diff;
    updateSolution();
   }
  }

  // check if currentIndex == n and return
  if (currentIndex >= n)
   return;

  // add curindex to selected
  selected[currentIndex] = true;
  solve(currentIndex + 1);

  // remove curindex from selected
  selected[currentIndex] = false;
  solve(currentIndex + 1);
 }

 protected static void updateSolution() {
  for (int i = 0; i < n; i++) {
   solution[i] = selected[i];
  }
 }

 protected static void print() {
  for (int i = 0; i < n; i++) {
   if (solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
  for (int i = 0; i < n; i++) {
   if (!solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
 }

 protected static int getDiff() {

  int leftSum = 0;
  int rightSum = 0;

  for (int i = 0; i < n; i++) {
   if (selected[i])
    leftSum += a[i];
   else
    rightSum += a[i];
  }

  return Math.abs(rightSum - leftSum);
 }
}