46. Permutations

/*
 * we need to know what position we are, and what letters we can use
 * we use a boolean array to keep track of what letters have currently being used
 * and loop through all possible letters
 */

class Solution {

  public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> sol = new ArrayList<List<Integer>>();
    Integer[] p = new Integer[nums.length];
    boolean[] isUsed = new boolean[nums.length];

    permute(nums, sol, p, isUsed, 0);

    return sol;
  }

  public void permute(int[] nums, List<List<Integer>> sol, Integer[] p, boolean[] isUsed, int index) {
    if (index >= nums.length) {
      sol.add(Arrays.asList(p.clone()));
    }

    for (int i = 0; i < nums.length; i++) {
      if (isUsed[i]) continue;

      isUsed[i] = true;
      p[index] = nums[i];
      permute(nums, sol, p, isUsed, index + 1);
      isUsed[i] = false;
    }
  }
}