A good way into this one is to ask: what do we need to remember so we never redo work blindly? For 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls, the solution in this repository is mainly a backtracking solution.
Guide
What?
The code is easier to read if we treat it as a controlled search through possible states. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: backtracking.
The notes already sitting in the source point us in the right direction:
- backtracking
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are perm, backtrack, getProbability, firstHalf.
Guide
Why?
The code is doing bookkeeping so your brain does not have to keep the entire search space open at once.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//backtracking
02/*
03the ideas is to permute the "balls"(containing count of each colors),
04rather than permute the array "nums" containing all balls to avoid TLE
05
06e.g.
07balls = [1,3,2]
08nums = [0, 1, 1, 1, 2, 2]
09*/
10//https://leetcode.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/discuss/661723/Struggling-with-probability-problems-Read-this.
11//the function perm() borrows from https://leetcode.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls/discuss/661730/C%2B%2B-Backtrack-with-explanation
12//Runtime: 1336 ms, faster than 100.00% of C++ online submissions for Probability of a Two Boxes Having The Same Number of Distinct Balls.
13//Memory Usage: 6.7 MB, less than 100.00% of C++ online submissions for Probability of a Two Boxes Having The Same Number of Distinct Balls.
14class Solution {
15public:
16 //use double to avoid overflow
17 double good, all;
18
19 double perm(vector<int>& v){
20 /*
21 v contains the count of balls of different colors
22 e.g. v = [1, 3, 2] means the balls are 0, 1, 1, 1, 2, 2
23 this function return the permutation count,
24 i.e. 6!/(1!3!2!),
25 here we calculate 6! by multiplying nom with ans while nom increasing,
26 we calculate 1!, 3!, 2! by dividing ans by denom from 1 to v[i] for all i
27 */
28 // cout << "calculating perm of : " << endl;
29 // for(int e : v){
30 // cout << e << " ";
31 // }
32 // cout << endl;
33
34 double ans = 1;
35 int nom = 1;
36 for(int i = 0; i < v.size(); i++){
37 for(int denom = 1; denom <= v[i]; denom++){
38 ans = ans * nom /denom;
39 // cout << " * " << nom << " / " << denom << endl;
40 nom++;
41 }
42 }
43 // cout << "perm of v: " << ans << endl;
44 return ans;
45 };
46
47 void backtrack(vector<int>& balls, vector<int>& firstHalf, vector<int>& secondHalf, int cur){
48 if(cur == balls.size()){
49 //stop condition
50 if(accumulate(firstHalf.begin(), firstHalf.end(), 0) !=
51 accumulate(secondHalf.begin(), secondHalf.end(), 0)){
52 //their count should be the same!
53 return;
54 }
55
56 //use double to avoid overflow
57 double perm1 = perm(firstHalf);
58 double perm2 = perm(secondHalf);
59
60 all += perm1 * perm2;
61
62 //check if their distinct color counts are the same
63 int dcount1 = count_if(firstHalf.begin(), firstHalf.end(),
64 [](const int& x){
65 return x != 0;
66 });
67 int dcount2 = count_if(secondHalf.begin(), secondHalf.end(),
68 [](const int& x){
69 return x != 0;
70 });
71 good += (dcount1 == dcount2) ? perm1 * perm2 : 0;
72 }else{
73 //continue until cur == balls.size()
74 /*
75 for the color "cur",
76 there are balls[cur] balls of this color,
77 distribute i balls to firstHalf,
78 and the remaining to secondHalf
79 */
80 for(int i = 0; i <= balls[cur]; i++){
81 firstHalf[cur] = i;
82 secondHalf[cur] = balls[cur] - i;
83 backtrack(balls, firstHalf, secondHalf, cur+1);
84 }
85 }
86 };
87
88 double getProbability(vector<int>& balls) {
89 good = all = 0;
90 int n = balls.size();
91 vector<int> firstHalf(n, 0), secondHalf(n, 0);
92 backtrack(balls, firstHalf, secondHalf, 0);
93 return good/all;
94 }
95};Cost