午间课堂¶

Graph¶

Subset Problem¶

Not asking for total number, but ask for each configuration.
When each element can have only two possibability: count or not count, then it's a subset problem.

void findSubset(int idx, vector<int>& nums, vector<int>& curr) {
    if (idx == nums.size()) {
        cout << curr << endl;
        return ;
    }

    curr.push_back(nums[idx]);
    findSubset(idx + 1, nums, curr);
    curr.pop_back(); // revoke back
    findSubset(idx + 1, nums, curr);
}

void solve(vector<int>& nums) {
    vector<int> curr;
    findSubset(0, nums, curr);
}

Why cannot swap?

curr.push_back(nums[idx]);
findSubset(idx + 1, nums, curr);
curr.pop_back(); // revoke back
findSubset(idx + 1, nums, curr);

cannot be:

findSubset(idx + 1, nums, curr);
curr.push_back(nums[idx]);
findSubset(idx + 1, nums, curr);

Answer: it will only push and not pop, so when finishing the recursion, the node will contain the previous character/number.
Rule of thumb: push times == pop times

With duplicate elements¶

each subset can have multiple same element

e.g. given nums = {a, b1, b2, c} a: 0 or 1 b: 0, 1 or 2 c: 0 or 1

so there are $2 \times 3 \times 2$ possible configurations

the recusion tree will look like:

a ---              {a} | {}
b ---{a} {a,b} {a,b,b} | {} {b} {b,b}
c ---...

vector<vector<int>> res;
void dfs(int idx, vector<int>& nums, vector<int>& curr) {
    if (idx == nums.size()) {
        res.push_back(curr);
        return;
    }
    curr.push_back(nums[idx]);
    dfs(idx + 1, nums, curr);
    curr.pop_back();
    int next = idx;
    while (next < nums.size() && nums[next] == nums[idx])
        next++;
        dfs(next, nums, curr);
    }

vector<vector<int>> subsetsWithDup(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<int> curr;
    dfs(0, nums, curr);
    return res;
}

Split array into two parts s.t. each part sum is equal to the other¶

calculate the total sum
then our target sum is sum / 2, our task is to find the combination

#include <bits/stdc++.h>

using namespace std;

void helper(vector<int>& num, int idx, int sum, vector<int>& curr) {
  if (sum == 0) {
    for (int c : curr) printf("%d ", c);
    cout << endl;
    return;
  }
  if (idx == num.size()) return;
  curr.push_back(num[idx]);
  helper(num, idx + 1, sum - num[idx], curr);
  curr.pop_back();
  helper(num, idx + 1, sum, curr);
}

void solve(vector<int>& nums) {
  int sum = 0;
  for (int c : nums) sum += c;
  sum /= 2;
  vector<int> curr;
  helper(nums, 0, sum, curr);
}

int main() {
  int n;
  cin >> n;
  vector<int> num(n);
  for (int i = 0; i < n; ++i) cin >> num[i];
  solve(num);
  return 0;
}

Note: this code will check all the possible sum: e.g. given array 1, 1, 1, 1 -> 1, 1 | 1, 1 | 1, 1 | 1, 1 since these are all the valid configurations (different 1s though)

To determine if possible (without enumerating all the configurations, which means you can terminate early):

#include <bits/stdc++.h>

using namespace std;

bool helper(vector<int>& num, int idx, int sum, vector<int>& curr) {
  if (sum == 0) {
    for (int c : curr) printf("%d ", c);
    cout << endl;
    return true;
  }
  if (idx == num.size()) return false;
  curr.push_back(num[idx]);
  if (helper(num, idx + 1, sum - num[idx], curr)) return true;
  curr.pop_back();
  if (helper(num, idx + 1, sum, curr)) return true;
}

void solve(vector<int>& nums) {
  int sum = 0;
  for (int c : nums) sum += c;
  sum /= 2;
  vector<int> curr;
  helper(nums, 0, sum, curr);
}
int main() {
  int n;
  cin >> n;
  vector<int> num(n);
  for (int i = 0; i < n; ++i) cin >> num[i];
  solve(num);
  return 0;
}

Variant: find minimal diff for the two subset sum¶

#include <bits/stdc++.h>

using namespace std;
int gDiff = INT_MAX;

void helper(vector<int>& num, int idx, int curr, int sum) {
  if (idx == num.size()) return ;
  curr += num[idx];
  gDiff = min(gDiff, abs((sum - curr) - curr));  
  helper(num, idx + 1, curr, sum);
  curr -= num[idx];
  helper(num, idx + 1, curr, sum);
}

void solve(vector<int>& nums) {
  int sum = 0;
  for (int c : nums) sum += c;
  vector<int> curr;
  helper(nums, 0, 0, sum);
}
int main() {
  int n;
  cin >> n;
  vector<int> num(n);
  for (int i = 0; i < n; ++i) cin >> num[i];
  solve(num);
  cout << gDiff;
  return 0;
}

Note: we don't need to maintain a list to save current configuration, just use an int curr to keep track of the current sum is fine.

Find all combination of size k¶

assume no duplication
base case: curr.size() == k

#include <bits/stdc++.h>

using namespace std;
void findSubset(int idx, int k, vector<int>& nums, vector<int>& curr) {
  if (curr.size() == k) {
    for (int c : curr) printf("%d ", c);
    cout << endl;
    return;
  }
  if (idx == nums.size()) return;
  curr.push_back(nums[idx]);
  findSubset(idx + 1, k, nums, curr);
  curr.pop_back();  // revoke back
  findSubset(idx + 1, k, nums, curr);
}

void solve(vector<int>& nums, int k) {
  vector<int> curr;
  findSubset(0, k, nums, curr);
}
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> num(n);
  for (int i = 0; i < n; ++i) cin >> num[i];
  solve(num, k);
  return 0;
}

Insert whitespaces into string¶

Should print all the configurations

Same logic as subset problem, now you have word.size() branches and each branch can either choose add or not add character to the current configuration.

Sliding window

maintain a sliding window which contains previous 6 elements.
for each iterations, check position from current position to i - 5 elements, if they are all space, don't add, or add space.

Graph 2¶

Parenthesis Problem¶

P1: ()()() given the provided parenthesis, find all valid permutations.¶

vector<string> res;
void helper(int open, int close, int total, string& curr) {
    if (curr.size() == total * 2) {
        res.push_back(curr);
        return ;
    }
    if (close < open)
        helper(open, close + 1, total, curr + ')');
    if (open < total)
        helper(open + 1, close, total, curr + '(');
}

vector<string> solve(int c) {
    string curr;
    helper(0, 0, c, curr);
    return res;
}

what if?

vector<string> res;

bool checkIfValid(string& curr) {
    // do the check for if open 
    // and close parentheses are the same amount
    stack<char> st;
    for (char c : s) {
        if (st.empty() || c == '(')
            st.push(c);
        else 
            st.pop();
    }
    return st.empty();
}

void helper(int open, int close, int total, string& curr) {
    if (checkIfValid(curr) == false) return ;
    if (curr.size() == total * 2) {
        res.push_back(curr);
        return ;
    }
    helper(open, close + 1, total, curr + ')');
    helper(open + 1, close, total, curr + '(');
}

vector<string> solve(int c) {
    string curr;
    helper(0, 0, c, curr);
    return res;
}

ans: it will work but DON'T do check in BASE case! (unnecessary overhead)

P2: given ((()) find how many more (minimal) parenthese to be added to make it valid¶

int solve(string& s) {
    stack<char> st;
    for (char c : s) {
        if (st.empty() || c == '(')
            st.push(c);
        // only pop if can make into a pair
        else if (st.top() == '(') 
            st.pop();
    }
    return st.size();
}

public int solve(String s){
    Deque<Character> stack = new ArrayDeque<>();
    int count = 0;
    for(char c : s.toCharArray()){
        if(c=='('){
            stack.offerFirst(c);
        }
        else{
            if(stack.isEmpty()){
                count++;
            }
            else{
                stack.pollFirst();
            }
        }
    }
    return count+stack.size();

}

P3: given a string contains {}, try to find the minimal number of curly braces that are needed to be reversed to make it valid¶

check this link 1. {} -> 0 2. {}}{ -> 2 3. {}} -> -1 (not possible)

int solve(string s) {
    stack<char> st;
    for (char c : s) {
        if (st.empty() || c == '(')
            st.push(c);
        // only pop if can make into a pair
        else if (st.top() == '(') 
            st.pop();
    }
    // not possible 
    if (st.size() % 2 == 1) 
        return -1; 
    if (st.empty()) 
        return 0;
    int cnt = 0;
    while (!st.empty() && st.top() == '(') {
        st.pop();
        cnt ++;
    }

    // open and close not match in size
    if (st.size() != cnt) 
        return -1; 
    return st.size();

}

P4: followup for P3, what if we can use `[]{}()`?¶

ans: use a map to set the mappings, where the key is opening bracket, and value is closing bracket.

P5: split array into k subarray s.t. each subarray shares the same sum.¶

here and here

vector<vector<vector<int>>> res;
void helper(vector<vector<int>>& sol, vector<int>& curr, int sum, int target, int idx, int level, vector<int>& nums) {
    if (level == 0) {
        res.push_back(sol);
        return ;
    }
    if (idx >= nums.size()) return;
    while (sum < target) {
        curr.push_back(nums[idx]);
        helper(sol, curr, sum + nums[idx], target, idx + 1, level - 1, nums);
        curr.pop_back();
        helper(sol, curr, sum, target, idx + 1, level - 1, nums);
    } 
    // now move on to next subarray
    if (sum == target) {
        vector<int> newCurr;
        sol.push_back(curr);
        helper(sol, newCurr, 0, target, idx + 1, level - 1, nums);
        sol.pop_back();
    }
}
vector<vector<vector<int>>> 
solve(vector<int>& nums, int k) {
    int m = nums.size(), n = nums[0].size();
    int sum = accumlate(nums.begin(), nums.end(), 0);
    sum /= k;
    vector<vector<int>> sol;
    vector<int> curr;
    helper(sol, curr, 0, sum, 0, 0, nums);
    return res;
}

public List<List<Integer>> solve(int[] array, int k){
    int sum = 0;
    for(int a : array){
        sum+=a;
    }
    List<Integer> sol = new ArrayList<>();
    List<List<Integer>> result = new ArrayList<>();
    int target = sum/k;

    dfs(array, 0, k,target, sol, result);

    return result;
}

private void dfs(int[] array, int start, int k, int target, List<Integer> sol, List<List<Integer>> result){
    if(start==array.length){
        if(sol.size()==k-1){
            result.add(sol);
        }
        return;
    }

    int sum = 0;
    for(int i = start; i<array.length; i++){
        sum+=array[i];

        if(target==sum){
            sol.add(i);
            dfs(array, i+1, k, target, sol, result);
            sol.remove(sol.size()-1);
        }
    }

}

Last update: January 9, 2021