Easy and clean backtracking


  • 0

    Use an boolean array to indicate which number is used. In this way we can make sure one number is added to list only once.

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

Log in to reply
 

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