Hello guys, this a DFS solution to the permutations problem on LeetCode
Stay tuned for a Dynamic programming solution!!!
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); } } }
No comments:
Post a Comment