Summary Codes :-)

• Subsets vs Subsets II
• Search in Rotated Sorted Array vs Search in Rotated Sorted Array II

Subsets

``````    iterative
public List<List<Integer>> subsets(int[] nums) {

ArrayList<List<Integer>> ans = new ArrayList<>();
if(nums.length == 0) return ans;

for(int num: nums){
int size = ans.size();
for(int i = 0; i < size; i ++){
List<Integer> tmp = new ArrayList<>(ans.get(i));
}
}

return ans;
}
``````
``````    recursive
public List<List<Integer>> subsets(int[] nums) {

ArrayList<List<Integer>> ans = new ArrayList<>();
if(nums.length == 0) return ans;

List<Integer> sub = new ArrayList<>();
dfs(nums, 0, sub, ans);
return ans;
}

public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans) {

if(start > nums.length)
return;

for(int i = start; i < nums.length; i ++){
dfs(nums, i + 1, sub, ans);
sub.remove(sub.size() - 1);
}
}
``````
``````    bit manipulation
public List<List<Integer>> subsets(int[] nums) {

ArrayList<List<Integer>> ans = new ArrayList<>();
if(nums.length == 0) return ans;

int n = 1 << nums.length;
for(int i = 0; i < n; i ++){
}
return ans;
}

public List<Integer> getSub(int[] nums, int k) {

List<Integer> subs = new ArrayList<>();

int index = 0;
for(int i = k; i > 0; i = i>>1){

if((i & 1) == 1)
index++;
}
return subs;
}
``````

Subsets II(contain duplicates)

``````   iterative
public List<List<Integer>> subsetsWithDup(int[] nums) {

ArrayList<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);

int size = 0;
for(int i = 0; i < nums.length; i ++){
int start = i > 0 && nums[i-1] == nums[i]? size :  0;

size = ans.size();
for(int j = start; j < size; j ++){
List<Integer> tmp = new ArrayList<>(ans.get(j));
}
}

return ans;
}
``````
``````    recursive
public List<List<Integer>> subsetsWithDup(int[] nums) {

ArrayList<List<Integer>> ans = new ArrayList<>();
List<Integer> sub = new ArrayList<>();

Arrays.sort(nums);
dfs(nums, 0, sub, ans);
return ans;
}

public void dfs(int[] nums, int start, List<Integer> sub, ArrayList<List<Integer>> ans){

for(int i = start; i < nums.length; i ++){

if(i > start && nums[i] == nums[i-1]) continue;
dfs(nums, i + 1, sub, ans);
sub.remove(sub.size() - 1);
}
}
``````

Search in Rotated Sorted Array

``````    public int search(int[] nums, int target) {

if(nums.length == 0) return -1;

int left = 0;
int right= nums.length - 1;

while(left <= right){

int mid = (left + right) / 2;
if(nums[mid] == target)
return mid;

if(nums[mid] >= nums[left]){
if(nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else{
if(nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right= mid - 1;
}
}

return -1;
}
``````

Search in Rotated Sorted Array II (allow dup)

``````    public boolean search(int[] nums, int target) {

if(nums.length == 0) return false;

int left = 0;
int right= nums.length - 1;

while(left <= right){

int mid = (left + right) / 2;
if(nums[mid] == target)
return true;

if(nums[mid] > nums[left]){
if(nums[left] <= target && target < nums[mid])
right = mid - 1;
else
left = mid + 1;
}
else if (nums[mid] < nums[left]){
if(nums[mid] < target && target <= nums[right])
left = mid + 1;
else
right= mid - 1;
}
else
left++;
}

return false;
}
``````

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