#Backtracking#

Leave a comment

November 20, 2016 by oneOokay

NOTE:

  • List<List<Integer>> ans = new ArrayList<>();
  • ans.add(new ArrayList<>(list));
  • list.remove(index)
  • list.contains(element)

Subsets I: NO duplicates in nums

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

找到一个集合中的所有子集,子集里面元素是可以小于nums.length的(并不一定要取所有的数字)(所以helper method里面要传入index)

help method:

  • helper method 传入index(因为子集元素 <= nums.length)
  • add tmpList to result in helper method everytime
  • helper里面的for-loop每次都从index开始
  • helper method里面递归的时候传入i + 1
  • remove last element that added.
public class Solution {
    public List subsets(int[] nums) {
        List ans = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return ans;
        }
        List list = new ArrayList();
        helper(0, list, ans, nums);
        return ans;
    }
    
    private void helper(int index, List list, List ans, int[] nums){
        ans.add(new ArrayList<>(list));
        for (int i = index; i < nums.length; i ++){
            list.add(nums[i]);
            helper(i + 1, list, ans, nums);
            list.remove(list.size() - 1);
        }
    }
}

Subsets II: nums contain duplicates

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

与SubsetsI相比就是多了重复的元素,需要考虑除重的问题。重复的元素且每个元素只能取一次,所以先sort array

helper method:

  • 同样需要传入index:因为子集中元素的个数会小于等于Nums.length
  • 每次都add tmpList to answer
  • for -loop i每次都从index开始
  • 首先在for loop中进行除重:如果i > index 且当前元素和前一个元素相等,则continue;
  • 接着call helper method传入index = i + 1
  • remove last element that added.
public class Solution {
    public List subsetsWithDup(int[] nums) {
        List ans = new ArrayList<>();
        if (nums == null || nums.length == 0){
            return ans;
        }
        Arrays.sort(nums);
        helper(0, new ArrayList(), ans, nums);
        return ans;
    }
    
    private void helper(int index, List tmpList, List ans, int[] nums){
        ans.add(new ArrayList(tmpList));
        
        for (int i = index; i < nums.length; i ++){
            if (i > index && nums[i] == nums[i - 1]){
                continue; //注意这里是continue 而不是return.
            }
            
            tmpList.add(nums[i]);
            helper(i + 1, tmpList, ans, nums);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

Permutations I: nums contains NO duplicates

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

求排列组合:每一个子集都包含于nums.length相同个数的元素,所以helper method里面不需要传入index,helper method里面每次都从i=0开始循环。

helper method:

  • 不需要传入index
  • helper method里面每次tmpList.size() == nums.length的时候,把它加入到ans中
  • for-loop:i每次都从0开始
  • 如果当前nums[i]不存在于tmpList中,那么将其加入;否则continue
  • call helper method: 传入i + 1
  • remove last elemented that is added.

Permutations II: nums contains duplicates

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

存在duplicates且每个元素都只能取一次,那么先sort array;由于排列组合子集中元素个数与Nums.length相同,helper method for loop扫的时候每次都从i=0开始扫,那么需要另一个数据结构来存储当前这个元素是否已经被加到tmpList里面了。

helper method:

  • 不用传入index,但需要传入boolean[] visited
  • 当tmpList.size() == nums.length的时候,将其加入到ans中
  • for loop每次都从i=0开始
  • 除重:跳过:这个元素已经visited或者这个元素是非第一个元素且与前一个元素值相同且前一个元素并没有visited
  • 加入元素到tmpList中更新与之对应的visited array
  • call helper method:传入tmpList和visited
  • 移除新加入的元素并且更新与之对应的visited array

Combination Sum


Letter Combinations of a Phone Number

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: