Tuesday, September 29, 2015

LeetCode Permutations DFS solution

Hello guys, this a DFS solution to the permutations  problem on LeetCode


public class Solution {
    
    public List<List<Integer>> permute(int[] nums) {
  List<List<Integer>> result = new LinkedList<List<Integer>>();
 
  List<Integer> numsList = new ArrayList<Integer>();
  for (int i = 0; i < nums.length; ++i) {
   // if (nums[i] != nums[j]) {
   numsList.add(nums[i]);
  }
  
  permuteDFS(numsList, result, new ArrayList<Integer>(), nums.length);
  return result;
 }

 private void permuteDFS(List<Integer> numbers, List<List<Integer>> result,
   List<Integer> stack, int k) {
  if (stack.size() == k) {
   List<Integer> entry = new ArrayList<Integer>(k);
   for (int i = 0; i < stack.size(); ++i) {
    entry.add(stack.get(i));
   }
   result.add(entry);
   return;
  }

  for (int i = 0; i < numbers.size(); ++i) {
   stack.add(numbers.get(i));

   // dfs on rest

   List<Integer> numsTemp = new ArrayList<Integer>();
   for (int j = 0; j < numbers.size(); ++j) {
    if (numbers.get(j) != numbers.get(i)) {
     numsTemp.add(numbers.get(j));
    }
   }
   permuteDFS(numsTemp, result, stack, k);

   stack.remove(stack.size() - 1);
  }
 }
}



Stay tuned for a Dynamic programming solution!!!

No comments:

Post a Comment