Count Good Subsets

The idea is to use a recursive approach to find all subsets of the array. The recursive idea is very clear that there are only two choices for any element in the array, either to include the element in the subset or do not include the element. Using this idea, we can find all subsets recursively, and we will check if the subset follows the given conditions.

We will define a function allSubsets(ARR, subset, index) to find all subsets of ARR. We will create an array subset to store the numbers present in the subset. Our final answer will be the total number of good subsets following the given conditions.

Working of the Recursive function: 

1. If index is equal to N, then we will check if the elements present in the array subsets follow the given conditions, then we will return 1. Otherwise, we will return 0. This will serve as the base case for our recursive function.
2. There are two cases for each element in the array ARR. The first case is when the element ARR[index] is not included in the subset. We will find firstAnswer, which is equal to allSubsets(ARR, subset, index+1).
3. The second case when the element ARR[index] is included in the subset. So, we will insert ARR[index] in the array subset, and we will find secondAnswer, which is equal to allSubsets(ARR, subset, index+1).
4. In the end, we will return firstAnswer + secondAnswer.

A simple method is to sort the given array and traverse through the array to find the total number of good subsets with each array element as the rear element of the subset.

Our approach will be to construct an array distinctSubsets to store the total number of subsets following the given condition with ARR[i] as the rear element of the subset. We will sort the array ARR. We will iterate index from 0 to N-1, and in each iteration, we will iterate pos from 0 to index-1. 

Now, there will be two cases,

1. If ARR[pos] divides ARR[index], then we can insert ARR[index] in those subsets in which the rear element is ARR[pos]. So, we will increment distinctSubsets[index] by distinctSubsets[pos]. 
2. If ARR[pos] does not divide ARR[index], then we cannot insert ARR[index] in those subsets in which the rear element is ARR[pos].

The subset elements can only be arranged in increasing order such that each element divides the next element in order. Due to this, we are sorting the array and traversing through the array to find the total number of subsets in which we can append the array element.

Algorithm:

• We will set totalSubsets as 0. The variable totalSubsets stores the total number of good subsets.
• Create an array distinctSubsets of size N with the value 1 at each position, which stores the total number of good subsets that can be created with each element of the array ARR as the rear element of the subset.
• Sort the array ARR.
• Iterate index from 0 to N-1,
  • Iterate pos from 0 to index-1,
    • We will check if ARR[index] can be divided by ARR[pos],
      • We will increment distinctSubsets[index] by distinctSubsets[pos].
  • Increment totalSubsets by distinctSubsets[index].
• Return the variable totalSubsets.

In the previous approach, we are traversing through the array to find the total number of subsets in which we can append the array element, but in this approach, we will be traversing through all the possible elements that we can append in the subset, i.e., its multiples. We are trying to create a subset such that each element divides the next element of the subset. So, our approach will be to traverse through all possible elements such that the rear element of the subset divides that particular element. 

We will construct an array distinctSubsets of size Max(ARR), and we will sort the array ARR. We will iterate index from 0 to N-1, and in each iteration, we will iterate pos from 2*ARR[index] to Max(ARR) and set element as ARR[index].

1. We are traversing through all possible values such that the value pos can be divided by element. So, we can insert pos in those sets whose rear element is element. We will increment distinctSubsets[pos] by distinctSubsets[element].
2. Increment pos by element.

Algorithm:

• We will set totalSubsets as 0 and maxElement as the maximum element in the array ARR. The variable totalSubsets stores the total number of good subsets.
• Create an array distinctSubsets of size maxElement+1 with value 1 at each position.
• Sort the array ARR.
• Iterate index from 0 to N-1,
  • We will set element as ARR[index] and set pos as 2*element.
  • Iterate till pos is less than or equal to maxElement,
    • Increment distinctSubsets[pos] by distinctSubsets[element].
    • Increment pos by element.
  • Increment totalSubsets by distinctSubsets[element].
• Return the variable totalSubsets.