Clean Java Backtrack solution


  • 0
    public class Solution {
        
        private List<Integer> clone(List<Integer> l) {
            List<Integer> newL = new ArrayList<Integer>();
            for(int i : l)
                newL.add(i);
            return newL;
        }
        
        private void helper(int[] nums, int i, List<Integer> curr, List<List<Integer>> res) {
            if(nums.length==i) {
                res.add(clone(curr));
            } else {
                int dupCount = 1;
                int val = nums[i];
                for(; i<nums.length-1; i++, dupCount++)
                   if(nums[i+1]!=nums[i])
                      break;
                for(int k=0; k<=dupCount; k++) {
                    for(int j=0; j<k; j++)
                        curr.add(val);
                    helper(nums,i+1,curr,res);
                    for(int j=0; j<k; j++)
                        curr.remove(curr.size()-1);
                }
            }
        }
        
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(nums.length==0)
                return res;
            Arrays.sort(nums);
            helper(nums,0,new ArrayList<Integer>(),res);
            return res;
        }
    }

Log in to reply
 

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