Java backtracking solution - 2 methods


  • 0
    M

    Method 1: use flag[]

    public class Solution {
    	public List<List<Integer>> permute(int[] nums) {
    		List<List<Integer>> res = new ArrayList<>();
    		List<Integer> list = new ArrayList<>();
    		boolean[] flag = new boolean[nums.length];
    		permute_recursion(flag, nums, list, res);
    		return res;
    	}
    	
    	private void permute_recursion(boolean[] flag, int[] nums, List<Integer> list, List<List<Integer>> res){
    		if(list.size()==nums.length){
    			res.add(new ArrayList<Integer>(list));
    			return;
    		}
    		for(int i=0; i<nums.length; i++){
    			if(flag[i]) continue;
    			flag[i] = true;
    			list.add(nums[i]);
    			permute_recursion(flag, nums, list, res);
    			list.remove(list.size()-1);
    			flag[i] = false;
    		}
    	}
    }
    

    Method 2: by swap

    public class Solution {
    	public List<List<Integer>> permute(int[] nums) {
    		List<List<Integer>> res = new ArrayList<>();
    		List<Integer> list = new ArrayList<>();
    		boolean[] flag = new boolean[nums.length];
    		permute_recursion(flag, nums, list, res);
    		return res;
    	}
    	
    	private void permute_recursion(boolean[] flag, int[] nums, List<Integer> list, List<List<Integer>> res){
    		if(list.size()==nums.length){
    			res.add(new ArrayList<Integer>(list));
    			return;
    		}
    		for(int i=0; i<nums.length; i++){
    			if(flag[i]) continue;
    			flag[i] = true;
    			list.add(nums[i]);
    			permute_recursion(flag, nums, list, res);
    			list.remove(list.size()-1);
    			flag[i] = false;
    		}
    	}
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.